首页 > 代码库 > ACDream - Graphs

ACDream - Graphs

2024-07-14 00:27:56   230人阅读

先上题目：

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

2 11 25 41 21 31 41 5

Sample Output

NOYES


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

上代码：

 1 #include <cstdio> 2 #include <cstring> 3 #define MAX 100002 4 using namespace std; 5   6 int c[MAX][3],p[MAX],d[MAX],a[MAX],co,n,m; 7   8 int findset(int u){ 9     return u==p[u] ? u : p[u]=findset(p[u]);10 }11  12 bool check_(int x,int y){13     int ans=0;14     for(int i=0;i<3;i++){15         if(c[x][i]==y) ans++;16         else{17             for(int j=0;j<3;j++){18                 if(c[x][i]==c[y][j]) ans++;19             }20         }21     }22     return ans<=1;23 }24  25 bool check(){26     co=0;27     for(int i=0;i<n;i++){28         if(d[i]>=4) return 1;29         else if(d[i]==3) a[co++]=i;30     }31     for(int i=0;i<co;i++){32         for(int j=i+1;j<co;j++){33             if(findset(a[i])==findset(a[j]) && check_(a[i],a[j])) return 1;34         }35     }36     return 0;37 }38  39 int main()40 {41     int u,v;42     //freopen("data.txt","r",stdin);43     while(scanf("%d %d",&n,&m)!=EOF){44         for(int i=1;i<=n;i++) p[i]=i;45         memset(d,0,sizeof(d));46         for(int i=0;i<m;i++){47             scanf("%d %d",&u,&v);48             if(d[u]<3) c[u][d[u]]=v;49             if(d[v]<3) c[v][d[v]]=u;50             d[u]++; d[v]++;51             u = findset(u);52             v = findset(v);53             if(u!=v) p[v]=p[u];54         }55         if(check()) printf("YES\n");56         else printf("NO\n");57     }58     return 0;59 }
Graphs

 


联系
我们