1298. 通讯问题

★★   输入文件：jdltt.in   输出文件：jdltt.out   简单对比

时间限制：1 s   内存限制：128 MB

【题目描述】

一个篮球队有n个篮球队员，每个队员都有联系方式（如电话、电子邮件等）。但并不是每个队员的联系方式都公开，每个队员的联系方式只有一部分队员知道。问队员可以分成多少个小组，小组成员之间可以相互通知（包括一个队员一个组，表示自己通知自己）。

【输入格式】

 

输入文件有若干行

第一行，一个整数n，表示共有n个队员(2<=n<=100)

下面有若干行,每行2个数a、b，a、b是队员编号，表示a知道b的通讯方式。

 

【输出格式】

 

输出文件有若干行

第一行，1个整数m，表示可以分m个小组，下面有m行，每行有若干个整数，表示该小组成员编号，输出顺序按编号由小到大。

 

【样例输入】

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

【样例输出】

 

 

8

1 2 3

4 6

5

7 8

9

10

11

12

 

裸题、、、、、（不要忘了排序、、、）　　

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 1000using namespace std;bool flag,vis[N],vist[N];int n,x,y,tot,ans,top,tim,sum;int low[N],dfn[N],head[N],stack[N],belong[N];struct Edge{    int from,to,next;}edge[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}    return x*f;}int add(int x,int y){    tot++;    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot;}int tarjan(int now){    dfn[now]=low[now]=++tim;    stack[++top]=now;vis[now]=true;    for(int i=head[now];i;i=edge[i].next)    {        int t=edge[i].to;        if(vis[t]) low[now]=min(low[now],dfn[t]);        else if(!dfn[t]) tarjan(t),low[now]=min(low[now],low[t]);        }    if(low[now]==dfn[now])    {        sum++;belong[now]=sum;        for(;stack[top]!=now;top--)        {            int x=stack[top];            belong[x]=sum;vis[x]=false;        }        vis[now]=false;top--;    }}int main(){    freopen("jdltt.in","r",stdin);    freopen("jdltt.out","w",stdout);    n=read();    while(scanf("%d%d",&x,&y)==2)       add(x,y);    for(int i=1;i<=n;i++)     if(!dfn[i]) tarjan(i);    printf("%d\n",sum);    for(int i=1;i<=n;i++)    {        flag=false;        if(!vist[i])         for(int j=1;j<=n;j++)          if(belong[j]==belong[i]) vist[j]=true,printf("%d ",j),flag=true;        if(flag) printf("\n");    }     return 0;}