连通图

题目

判断一个图是否为一个连通图

输入

n 顶点个数 ( n <= 100 )
点与点之间的边

输出

1 表示连通
0 表示不边通

样例

input

5
1 2
2 3
5 4
0 0

output

0

解题思路

建一个邻接表，从任意一个点走起，将所有点走一遍，如果能就输出 1 ，不能就输出 0 。

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
int n,x,y,tot,maxn;
int p[110],head[110];
struct c{int x,next;
}f[501];
int main()
{scanf("%d",&n);scanf("%d%d",&x,&y);while (x!=0&&y!=0){tot++;f[tot].x=x;f[tot].next=head[y];head[y]=tot;tot++;f[tot].x=y;f[tot].next=head[x];head[x]=tot;  //放入邻接表，无向图双向都存scanf("%d%d",&x,&y);}int ans=1,t=1;queue<int>s;s.push(1);p[1]=1;do{int y=s.front();  //取队首s.pop();  //弹出队首for (int j=head[y];j;j=f[j].next)if (p[f[j].x]==0)  //这个点没走过{t++;ans++;  //累加走过的点的个数p[f[j].x]=1;s.push(f[j].x);  //放入队尾}}while(s.size()>0);if (ans==n)  //走过的点的个数等于的点的个数，是连通图，否则不是cout<<1<<endl;else cout<<0<<endl;return 0;
}