Cod sursa(job #831028)

Utilizator Mitza444Vidrean Mihai Mitza444 Data 8 decembrie 2012 00:17:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<vector>
#include<stack>
#define MAX 100001
using namespace std;
struct nod{
    int index,lowlink;
}v[MAX];
vector <int> graf[MAX];
vector < vector <int> > ctc;
stack <int> S;
bool viz[MAX],inS[MAX];
int n,m,ind;
void strongconnect(int x){
	int i,vf;
    ind++;viz[x]=1;
    v[x].index=ind;
    v[x].lowlink=ind;
	S.push(x);inS[x]=1;
	for(i=0;i<(int)graf[x].size();i++){
		vf=graf[x][i];
		if(!viz[vf]){
			strongconnect(vf);
			v[x].lowlink=min(v[x].lowlink,v[vf].lowlink);
		}
		else if(inS[vf])
			v[x].lowlink=min(v[x].lowlink,v[vf].lowlink);
	}
	if(v[x].lowlink==v[x].index){
		vector <int> vec;
		while(S.top()!=x){
			vec.push_back(S.top());
			inS[S.top()]=0;
			S.pop();
		}
		vec.push_back(S.top());
		inS[S.top()]=0;
		S.pop();
		ctc.push_back(vec);
	}
}
void Tarjan(){
    int i;
    for(i=1;i<=n;i++)
        if(!viz[i])
            strongconnect(i);
}
int main(){
	int i,j,x,y;
    freopen("ctc.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        graf[x].push_back(y);
    }
	fclose(stdin);
	Tarjan();
	freopen("ctc.out","w",stdout);
	printf("%d\n",ctc.size());
	for(i=0;i<(int)ctc.size();i++){
		for(j=0;j<(int)ctc[i].size();j++)
			printf("%d ",ctc[i][j]);
		printf("\n");
	}
	fclose(stdout);
	return 0;
}