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行，每行有若干个整数，表示该小组成员编号，输出顺序按编号由小到大。

【样例输入】

12

1 3

2 1

2 4

3 2

3 4

3 5

4 6

5 4

6 4

7 4

7 8

7 12

8 7

8 9

10 9

11 10

【样例输出】

8

1 2 3

4 6

5

7 8

9

10

11

12

/*

Tarjan模板+缩点+sort

*/

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

#include<cstring>

#define MAXN 101

using namespace std;

struct data

{

    int v,next;

}

e[MAXN];

//vector<int>g[MAXN];

struct node

{

    int x[500];

    int l;

}

g[MAXN];

int n,m,cut,belong[MAXN],head[MAXN],dfn[MAXN],stack[MAXN],low[MAXN],in[MAXN],top,tot;

void init()

{

    cut=tot=top=0;

    memset(head,-1,sizeof(head));

    memset(stack,0,sizeof(stack));

    memset(dfn,0,sizeof(dfn));

    memset(low,0,sizeof(low));

    memset(in,0,sizeof(in));

}

void add_edge(int u,int v)

{

    e[tot].v=v;

    e[tot].next=head[u];

    head[u]=tot++;

}

void tarjan(int u)

{

    int v;

    low[u]=dfn[u]=++cut;

    in[u]=1;//当前节点进栈

    stack[top++]=u;

    for(int i=head[u];i!=-1;i=e[i].next)//遍历边

    {

        v=e[i].v;

        if(!dfn[v])//未被访问

        {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(in[v])

        {

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(dfn[u]==low[u])//找到一个强联通分量的根

    {

        int l=0,a[MAXN];

        tot++;

        do

        {

            v=stack[--top];//退栈

            in[v]=0;

            belong[v]=tot;//tot为连通分量编号

            a[++l]=v;

        }

        while(u!=v);

        sort(a+1,a+l+1);

        for(int i=1;i<=l;i++)

        {

            g[tot].x[i]=a[i];

        }

        g[tot].l=l;

    }

}

int cmp1(const node &x,const node &y)

{

    return x.x[1]<y.x[1];

}

int main()

{

    //freopen("jdltt.in","r",stdin);

    //freopen("jdltt.out","w",stdout);

    while(scanf("%d",&n)!=EOF)

    {

        int x,y;

        init();

        for(int i=1;i<=n;i++)

          g[i].l=0;

        while(scanf("%d %d",&x,&y)!=EOF)

        {

            add_edge(x,y);

        }

        tot=0;

        for(int i=1;i<=n;i++)

        {

            if(!dfn[i])

              tarjan(i);

        }

        cout<<tot<<endl;

        sort(g+1,g+tot+1,cmp1);

        for(int i=1;i<=tot;i++)

        {

            for(int j=1;j<=g[i].l;j++)

              printf("%d ",g[i].x[j]);

            printf("\n");

        }

    }

    return 0;

}