ACDream - Graphs

先上题目：

Graphs

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

SubmitStatus

Problem Description

给出N个点，M条边，问是否存在一个连通子图，子图由原图删掉一些点和边（不删亦可），且叶子数>=4（即度为1的点）

Input

多组数据，每组数据N,M(0 <= N <= 10000,0 <= M <= 20000)

接下来M行每行给出一条边的两个端点x,y (1 <= x ,y <= N)，保证无重边，无自环

Output

对于每组数据，输出YES，如果你能找到这样的子图，否则输出NO

Sample Input

Sample Output

NO

YES

　　根据题意，我们可以将点分成3种：①度小于3的点，②度等于3的点，③度大于等于4的点。
　　对于①，我们可以直接跳过，因为这种点无论是单个还是组合都无法产生符合要求的子图。对于②，如果有两个度为三的点连载一起并且重合的点小于等于1个的话就有可能产生符合要求的子图。对于③，一个点就可以引出符合要求的子图。
　　所以我们可以先判断是否有③的点，如果有就直接输出YES，否则判断所有度为③的点是否有符合要求的，如果有就直接输出YES,否则就不存在题目要求的子图。

上代码：

 #include <cstdio>

 #include <cstring>

 #define MAX 100002

 using namespace std;

 int c[MAX][],p[MAX],d[MAX],a[MAX],co,n,m;

 int findset(int u){

     return u==p[u] ? u : p[u]=findset(p[u]);

 }

 bool check_(int x,int y){

     int ans=;

     for(int i=;i<;i++){

         if(c[x][i]==y) ans++;

         else{

             for(int j=;j<;j++){

                 if(c[x][i]==c[y][j]) ans++;

             }

         }

     }

     return ans<=;

 }

 bool check(){

     co=;

     for(int i=;i<n;i++){

         if(d[i]>=) return ;

         else if(d[i]==) a[co++]=i;

     }

     for(int i=;i<co;i++){

         for(int j=i+;j<co;j++){

             if(findset(a[i])==findset(a[j]) && check_(a[i],a[j])) return ;

         }

     }

     return ;

 }

 int main()

 {

     int u,v;

     //freopen("data.txt","r",stdin);

     while(scanf("%d %d",&n,&m)!=EOF){

         for(int i=;i<=n;i++) p[i]=i;

         memset(d,,sizeof(d));

         for(int i=;i<m;i++){

             scanf("%d %d",&u,&v);

             if(d[u]<) c[u][d[u]]=v;

             if(d[v]<) c[v][d[v]]=u;

             d[u]++; d[v]++;

             u = findset(u);

             v = findset(v);

             if(u!=v) p[v]=p[u];

         }

         if(check()) printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

Graphs

巴特西

ACDream - Graphs

Graphs

Problem Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章