Cod sursa(job #712501)

Utilizator costyv87Vlad Costin costyv87 Data 13 martie 2012 15:36:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
FILE *f,*g;
stack <int> S;
int x,y,n,m,i,j,index=1,bf[100100];
vector <int> ax;
vector < vector <int> > sol;
vector < int > a[100100];
struct cp{int ind,mn; } v[100100];


void tarjan(int x) {
int i;
v[x].ind=v[x].mn=index;
S.push(x);
index++;
bf[x]=1;

for (i=0;i<a[x].size();i++) 
	if (!v[a[x][i]].ind) {
		tarjan(a[x][i]);
		v[x].mn=min(v[x].mn,v[a[x][i]].mn);
		}
	else 
		if (bf[a[x][i]]==1) {
			v[x].mn=min(v[x].mn,v[a[x][i]].mn);
			}
if (v[x].ind==v[x].mn) {
	ax.clear();
	int cn;
	do  {
		ax.push_back(cn=S.top()); 
		bf[cn]=0;
		S.pop();
		}
	while (cn!=x);
	sol.push_back(ax);
	}
}

int main() {
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");

fscanf(f,"%d%d",&n,&m);

for (i=1;i<=m;i++) {
	fscanf(f,"%d%d",&x,&y);
	a[x].push_back(y);
	}

for (i=1;i<=n;i++) 
	if (v[i].ind==0) 
		tarjan(i);
	
fprintf(g,"%d\n",sol.size());

for (i=0;i<sol.size();i++,fprintf(g,"\n")) 
	for (j=0;j<sol[i].size();j++)
		fprintf(g,"%d ",sol[i][j]);

fclose(g);
return 0;
}