Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 两次BFS遍历解决，貌似不算很难...

Posted by sailist at 2019-05-12 14:29:36 on Problem 3310
```第一次遍历的时候判环，遍历完判断连通，第二次遍历判断是否存在度大于1的节点的邻居度也大于1

#include<stdio.h>
#include<queue>
#include<stack>
#include<algorithm>
#include <cstring>
using namespace std;

int n,e;
int g[101][101];
int vis[101];
int d[101];

bool solve()
{
memset(d,0,sizeof(d));
queue<int> q;
q.push(1);

int cur;
while(!q.empty())// 求度
{
cur = q.front();
vis[cur] = 1;
q.pop();

int loop_count = 0;
for(int i = 1;i<=n;i++)
{
if(i!=cur && !vis[i] && g[cur][i])
{
d[cur]++;
d[i]++;
q.push(i);
}
if(i!=cur && vis[i] && g[cur][i])
{
loop_count ++;
}
}
if(loop_count>=2)
{
return false;
}
}
for(int i = 1;i<=n;i++)
{
if(!vis[i])
{
return false;
}
}

q.push(1);
while(!q.empty())
{
cur = q.front();
vis[cur] = 0;
q.pop();
if(d[cur] == 1)
{
for(int i = 1;i<=n;i++)
{
if(i!=cur && vis[i] && g[cur][i])
{
q.push(i);
}
}
}else
{
int count = 0;
for(int i = 1;i<=n;i++)
{
if(i!=cur && vis[i] && g[cur][i])
{
q.push(i);
}
if(i!=cur && d[i]>1 && g[cur][i])
{
count++;
}
}
if(count>2)
{
return false;
}
}
}

return true;
}
/**
* POJ 3310
* @return
*/

int main()
{
int i = 1;
while(1)
{

scanf("%d",&n);
if(!n)
{
break;
}
scanf("%d",&e);

memset(vis,0,sizeof(vis));
memset(g,0,sizeof(g));
int l,r;
for(int i = 0;i<e;i++)
{
scanf("%d",&l);
scanf("%d",&r);
g[l][r] = 1;
g[r][l] = 1;
}

bool res = solve();

if(res)
{
printf("Graph %d is a caterpillar.\n",i);
}else
{
printf("Graph %d is not a caterpillar.\n",i);
}
i++;
}

return 0;
}```

Followed by: