记录编号	245539	评测结果	AAAAA
题目名称	通讯问题	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-04-03 17:27:50	内存使用	0.34 MiB

/*-------------------------------------------------
*  Author:Rainboy
*  time: 2016-03-30 15:42
*  © Copyright 2016 Rainboy. All Rights Reserved.
*-------------------------------------------------*/


/* -----------
 *  原理,:一个分量里的点都可以互相访问
 * 算法实现:
 *      1.初始化 dfn[i], low[i]
 *      2.对i所有相临的结点j
 *          1.if !vis[j] dfs[j]
 *          2.if vis[j] low[i] =dfn[j]
 *      3.if dfn[i] = low[i]
 * */


#include <cstdio>
#include <cstring>
#include<iostream>
#define maxn 1000 //最多的点
using namespace std;
bool instack[maxn] ={0}; // =false

int low[maxn];
int dfn[maxn] ={0};
int color[maxn]; // color[i] 点i的强连通分量
int stack[maxn],top; // 自己维护的stack ,可以用 STL stack
int cnt =0,indexk=0;
//存图
int first[maxn];
int u[maxn],v[maxn],next[maxn];

void tarjan(int x){
    int j;
    dfn[x] = low[x] = ++indexk;
    instack[x] =true;
    stack[++top] = x;
    int e = first[x];
    for(; e != -1; e = next[e]){
        j = v[e];
        if( !dfn[j] ) // dnf[j] !=0 表示 这个点没有被访问过
        {
            tarjan(j);
            if(low[j] < low[x])
                low[x] = low[j];
        } 
        else if(instack[j] && dfn[j] < low[x])
            low[x] = dfn[j];
    }
	if(dfn[x] == low[x])
        {
            cnt++;
            do{
                j=stack[top--];
                instack[j] = false;
                color[j] = cnt;
            }
            while(j !=x);
        }
}

int main(){
   freopen("jdltt.in","r",stdin);
	freopen("jdltt.out","w",stdout);
    top = 0;
    int i,j,k;
	int T;
    memset(first,-1,sizeof(first));
    scanf("%d",&T);
    //读取图 这里用边集数组
    i=1;
	while( cin>>u[i]>>v[i]){
        next[i] = first[u[i]];
        first[u[i]] = i;
		i++;
    }
    for(i=1;i<=T;i++){ // 遍历所有点
        if(!dfn[i]) // 没有被访问过
            tarjan(i);
    }
    printf("%d\n",cnt);


	for(k=1;k<=T;k++)
	{
		int t=color[k];
		if(t!=0){
			for(j=k;j<=T;j++)
				if(color[j]==t){
					cout<<j<<" ";
					color[j]=0;
					}cout<<endl;				
				}
		}
    return 0;
}