Cod sursa(job #1936569)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 23 martie 2017 10:57:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
using namespace std;
 
FILE*IN,*OUT;
int N,M,Sort[MaxN],X,Y,Size=0,Total=0;
bool found[MaxN];
vector <int>Graph[MaxN],Reverse[MaxN],Comp[MaxN];
void DFS(int node)
{
	found[node]=true;
	for(int i=0;i<Graph[node].size();i++)
		if(!found[Graph[node][i]])DFS(Graph[node][i]);
	Sort[++Size]=node;
}
void DFS2(int node)
{
	found[node]=true;
	Comp[Total].push_back(node);
	for(int i=0;i<Reverse[node].size();i++)
		if(!found[Reverse[node][i]])DFS2(Reverse[node][i]);
}
int main()
{
    IN=fopen("ctc.in","r");
    OUT=fopen("ctc.out","w");

	fscanf(IN,"%d%d",&N,&M);

	for(int i=1;i<=M;i++)
		fscanf(IN,"%d%d",&X,&Y),Graph[X].push_back(Y),Reverse[Y].push_back(X);
	
	for(int i=1;i<=N;i++)
		if(!found[i])DFS(i);
	memset(found,0,sizeof found);
	for(int i=N;i>0;i--)
		if(!found[Sort[i]])
		{
			++Total;
			DFS2(Sort[i]);
		}
	fprintf(OUT,"%d\n",Total);
	for(int i=1;i<=Total;i++)
	{
		for(int j=0;j<Comp[i].size();j++)
			fprintf(OUT,"%d ",Comp[i][j]);
		fprintf(OUT,"\n");
	}
	return 0;
}