Cod sursa(job #2223602)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 20 iulie 2018 18:56:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<cstdio>
#include<vector>
using namespace std;
const int NMAX=100005;
vector<int> vec[NMAX];
vector<int> vec2[NMAX];
vector<int> ans[NMAX];
int viz1[NMAX],viz2[NMAX],st[NMAX];
int t,ntc,n;
void dfs1(int x) 
{
	viz1[x]=1;
	int a;
	for(int i=0; i<vec[x].size(); i++) 
    {
		a=vec[x][i];
		if(viz1[a]==0)
			dfs1(a);
	}
	t++;
	st[n+1-t]=x;
}
void dfs2(int x) 
{
	viz2[x]=1;
	ans[ntc].push_back(x);
	int a;
	for(int i=0; i<vec2[x].size(); i++) 
    {
		a=vec2[x][i];
		if(viz2[a]==0)
			dfs2(a);
	}
}
int main() 
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	int i,j,x1,x2,m;
	scanf("%d%d",&n,&m);
	for(i=1; i<=m; i++) 
    {
		scanf("%d%d",&x1,&x2);
		vec[x1].push_back(x2);
		vec2[x2].push_back(x1);
	}
	for(i=1; i<=n; i++) 
	{
		if(viz1[i]==0)
			dfs1(i);
	}
	for(i=1; i<=n; i++) 
	{
		if(viz2[st[i]]==0) 
		{
			ntc++;
			dfs2(st[i]);
		}
	}
	printf("%d\n",ntc);
	for(i=1; i<=ntc; i++) 
	{
		for(j=0; j<ans[i].size(); j++)
			printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}