连通图

发布于 2019-04-18  1006 次阅读


题目描述

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

输入

n 顶点 (n<=100)

5
1 2
2 3 
5 4
0 0

输出

1 表示连通
0 表示不边通

0

思路

从1开始枚举每一个点,每走到一个点ans++
并把当前点标记起来,最后如果全部点都走过(ans==n)就是连通的

#include 
using namespace std;
int a[1001][1001];
int f[10001];
int n,ans=1;
int dfs(int dep)
{
    for (int i=1;i<=n;i++)
        if (f[i]==0&&a[dep][i]==1)
        {   
            ans++;
            f[i]=1;
            f[dep]=1;
            dfs(i);
        }
}
int main()
{
    f[1]=1;
    scanf("%d",&n);
    int x,y;
    scanf("%d%d",&x,&y);
    while (x!=0&&y!=0)
    {
        a[x][y]=1;
        a[y][x]=1;
        scanf("%d%d",&x,&y);
    }
    dfs(1);
    if (ans==n) printf("1");
    else printf("0");
    return 0;
}

bfs

#include 
using namespace std;
int a[1001][1001];
int f[100001];
int t[100001],n,ans=1;
int bfs()
{
    int head=0,tail=1;
    t[1]=1;
    f[1]=1;
    while (head
]]>