图的连通性——folyd检验

http://www.rqnoj.cn/Problem_480.html
这个比较适用，先把连通图保存在了g[][],在用floyd转化到直观连通图，在多个连通图存到map[][]中，
特别的map[i][0]是放第i个连通图的顶点数，若定点为0，则把i放入map[i][1]
#include<stdio.h>
#include<string.h>

bool g[505][505];
int map[505][505];
int v[505]; 

int main()
{
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&g[i][j]);
            }
        }
        
        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(!g[i][j]&&g[i][k]&&g[k][j])
                        g[i][j]=1;
                }
            }
        }
        
        memset(v,0,4*(n+1));
        int add=1;
        for(i=1;i<=n;i++)
        {
            if(v[i]==0)
            {
                v[i]=add;
                for(j=1;j<=n;j++)
                {
                    if(g[i][j]==1)
                        v[j]=add;
                }
                add++;
            }
        }
        
        int chang=add-1,nei;
        add=1;
        
        for(i=1;i<=n;i++)
        {
            if(v[i]==add)
            {
                nei=1;
                for(j=1;j<=n;j++)
                {
                    if(g[i][j]==1)
                    {
                        map[add][nei]=j;
                        nei++;
                    }
                }
                if(nei!=1)
                map[add][0]=nei-1;
                else
                {
                    map[add][1]=i;
                    map[add][0]=1;
                }
                add++;
            }
        }

        printf("%d\n",chang);
        for(i=1;i<=chang;i++)
        {
            for(j=1;j<=map[i][0];j++)
            {
                printf("%d ",map[i][j]);
            }
            printf("\n");
        }
    }
}