Cod sursa(job #752552)

Utilizator Marius96Marius Gavrilescu Marius96 Data 28 mai 2012 21:18:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<vector>
#include<stack>
using std::vector;
using std::stack;
using std::min;

vector<int> v[100005];
int         x[100005];
int         l[100005];
bool     inst[100005];
int cur=1;
stack<int> st;
vector<vector<int> > r;

void sc (int i)
{
	x[i]=l[i]=cur++;
	st.push (i);
	inst[i]=1;
	for(vector<int>::iterator it=v[i].begin();it!=v[i].end();it++)
		if(!x[*it]){
			sc (*it);
			l[i]=min (l[i],l[*it]);
		} else if (inst[*it])
			l[i]=min (l[i],x[*it]);
	if(x[i]==l[i]){
		vector<int> w;
		int c;
		do{
			c=st.top();
			st.pop();
			inst[c]=0;
			w.push_back (c);
		}while(c!=i);
		r.push_back (w);
	}
}

int main()
{
	freopen ("ctc.in","r",stdin);
	freopen ("ctc.out","w",stdout);
	int n,m;
	scanf ("%d %d",&n,&m);
	while(m--){
		int x,y;
		scanf ("%d%d",&x,&y);
		v[x].push_back (y);
	}

	for(int i=1;i<=n;i++)
		if(!x[i])
			sc (i);
	printf ("%lu",r.size());
	for(vector<vector<int> >::iterator it=r.begin();it!=r.end();it++){
		puts ("");
		for(vector<int>::iterator jt=it->begin();jt!=it->end();jt++)
			printf ("%d ",*jt);
	}
	return 0;
}