Cod sursa(job #632325)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 10 noiembrie 2011 21:14:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<cstdio>
#include<vector>
#include<deque>
using namespace std;

int n,m,x,y,scc,i,T,index[100010],lowlink[100010],S[100010];
vector<int> SCC[100010],G[100010];
deque<int>  Stack;

void read(),solve(),strongconnect(int);

int main()
{
	read();
	solve();
	
	return 0;
}

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

void solve()
{
	for(i=1;i<=n;i++)
	{
		if(!index[i])
			strongconnect(i);
	}
	printf("%d\n",scc);
	for(i=1;i<=scc;i++)
	{
		for(vector<int>::iterator it=SCC[i].begin();it!=SCC[i].end();it++)printf("%d ",*it);
		printf("\n");
	}
}

void strongconnect(int nod)
{
	T++;
	index[nod]=T;
	lowlink[nod]=T;
	Stack.push_back(nod);
	S[nod]=1;
	for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
	{
		//daca nu e vizitat, vizitez fiul
		if(!index[*it])
		{
			strongconnect(*it);
			lowlink[nod]=min(lowlink[nod],lowlink[*it]);
		}
		//daca fiul e in stiva, actualizez lowlink
		else if(S[*it])
			lowlink[nod]=min(lowlink[nod],index[*it]);
	}
	if(index[nod]==lowlink[nod])
	{
		//introduc elementul in componenta tare conexa
		int w=Stack.back();
		SCC[++scc].push_back(w);
		//scot nodul din stiva
		Stack.pop_back();
		S[w]=0;
		while(nod!=w)
		{
			w=Stack.back();
			Stack.pop_back();
			S[w]=0;
			SCC[scc].push_back(w);
		}
	}
}