Cod sursa(job #444291)

Utilizator nandoLicker Nandor nando Data 19 aprilie 2010 21:41:57
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
using namespace std;

FILE* fin=fopen("ctc.in","r");
FILE* fout=fopen("ctc.out","w");

#define MAXN 100010

typedef vector<int>::iterator iter;

int index[MAXN],lowlink[MAXN];
vector<vector<int> > ctc;
bitset<MAXN> inStack;
vector<int> g[MAXN],comp;
stack<int> s;

int n,m,idx=1;


void tarjan(int nod){
	index[nod]=lowlink[nod]=idx;
	idx++;
	s.push(nod),inStack[nod]=true;
	
	for(iter it=g[nod].begin();it!=g[nod].end();it++){
		if(index[*it]==-1){
			tarjan(*it);
			lowlink[nod]=min(lowlink[nod],lowlink[*it]);
		}else if(inStack[*it]){
			lowlink[nod]=min(lowlink[nod],lowlink[*it]);
		}				
	}
	
	
	if(index[nod]==lowlink[nod]){
		int snod;
		comp.clear();
		do{
			snod=s.top(),s.pop(),inStack[snod]=false;;
			comp.push_back(snod);
		}while(snod!=nod);
		ctc.push_back(comp);
	}
}

int main(){
	
	fscanf(fin,"%d %d\n",&n,&m);
	
	for(int i=1;i<=n;i++){
		index[i]=-1;
	}	
	
	int x,y;
	for(int i=1;i<=m;i++){
		fscanf(fin,"%d %d\n",&x,&y);
		g[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		if(index[i]==-1){
			tarjan(i);	
		}
	}
	
	fprintf(fout,"%d\n",ctc.size());
		
	for(int i=0;i<ctc.size();i++){
		for(iter it=ctc[i].begin();it!=ctc[i].end();++it){
			fprintf(fout,"%d ",*it);
		}
		fputc('\n',fout);
	}
	
	fclose(fin);
	fclose(fout);		
	return 0;
}