Cod sursa(job #1460586)

Utilizator SilviuIIon Silviu SilviuI Data 13 iulie 2015 12:06:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <vector>
#include <cstring>
#include <stack>
#include <bitset>
#define nmax 100010
using namespace std;
int n,m,i,j,x,y,nr,fr[nmax];
vector <int> g[nmax],gt[nmax],sol[nmax];
stack <int> st;
void dfs(int x)
{
	int i; fr[x]=1;
	for (i=0;i<g[x].size();i++) 
	    if (fr[g[x][i]]==0) dfs(g[x][i]);
	st.push(x);
}
void dfss(int x)
{
	int i; fr[x]=1; sol[nr].push_back(x);
	for (i=0;i<gt[x].size();i++)
	    if (fr[gt[x][i]]==0) dfss(gt[x][i]);
}
int main(){
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;i++) {
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		gt[y].push_back(x);
	}
	for (i=1;i<=n;i++)
	   if (fr[i]==0) dfs(i);
	memset(fr,0,sizeof(fr));
	while (!st.empty()) {
		if (fr[st.top()]==0) nr++,dfss(st.top());
		st.pop();
	}
	printf("%d\n",nr);
	for (i=1;i<=nr;i++) {
		for (j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]);
		printf("\n");
	}
	return 0;
}