Cod sursa(job #580798)

Utilizator bog29Antohi Bogdan bog29 Data 13 aprilie 2011 15:21:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#include<vector>
#include<stack>
#define dmax 100003
using namespace std;

int n,m,nrc;
bool t[dmax];

vector<int>g[dmax],gt[dmax],comp[dmax];
vector<int>::iterator it;

stack<int>st;


void dfs1(int k)
{	
	vector<int>::iterator ir;
	
	for(ir = g[k].begin(); ir < g[k].end(); ir++)
		if(!t[*ir])
		{	
			t[*ir] = 1;
			dfs1(*ir);
			st.push(*ir);
		}	
}

void dfs2(int k)
{	
	vector<int>::iterator ir;
	
	for(ir = gt[k].begin(); ir < gt[k].end(); ir++)
		if(t[*ir])
		{	
			t[*ir] = 0;
			comp[nrc].push_back(*ir);
			dfs2(*ir);
		}	
}

void ctc()
{	
	int i,x;
	
	for(i=1; i<=n; i++)
		if(!t[i])
		{	
			t[i] = 1;
			dfs1(i);
			st.push(i);
		}	
	
	while(!st.empty() )
	{	
		while(!st.empty() && !t[st.top()])
			st.pop();
		
		if(!st.empty() )
		{	
			nrc++;
			x = st.top();
			comp[nrc].push_back(x);
			t[x] = 0;
			dfs2(x);
		}	
	}
}


int main()
{	
	freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
	
	int i,a,b;
	
	scanf("%d %d", &n, &m);
	
	for(i=1;i<=m;i++)
	{	
		scanf("%d %d", &a, &b);
		g[a].push_back(b);
		gt[b].push_back(a);
	}	

	ctc();
	
	
	printf("%d\n", nrc);
	for(i=1; i<=nrc; i++)
	{	for(it = comp[i].begin(); it < comp[i].end(); it++)
			printf("%d ", *it);
		
		printf("\n");
	}	

	return 0;
}