Cod sursa(job #2263408)

Utilizator ionicaion ionica Data 18 octombrie 2018 17:43:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb

#include <fstream>
#include <vector>

#define MN 100001

using namespace std;

int viz[MN],n,m,k,nrctc;
int postordine[MN];

vector <int> G[MN];
vector <int> GT[MN];
vector <int> CTC[MN];


void DFS(int x)
{
    int i,j;
	viz[x]=1;
	for(i=0;i<G[x].size();i++)
		{
		    j=G[x][i];
		    if(!viz[j])
                DFS(j);
		}
	postordine[++k]=x;
}

void DFST(int x)
{
    int i,j;
	viz[x]=1;
	CTC[nrctc].push_back(x);
	for(i=0;i<GT[x].size();i++)
		{
		    j=GT[x][i];
		    if(!viz[j])
                DFST(j);
		}
}

int main(int argc,char *argv[])
{
	int n,m,x,y,i,j;
	ifstream fin("ctc.in");
	ofstream fout("ctc.out");

	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}

	for(i=1;i<=n;++i)
		if(!viz[i])
            DFS(i);

	for(i=1;i<=n;i++)
        viz[i]=0;

	for(i=n;i>=1;i--)
		if(!viz[postordine[i]])
        {
            nrctc++;
            DFST(postordine[i]);
        }

	fout<<nrctc<<'\n';
	for(i=1;i<=nrctc;i++)
	{
		for(j=0;j<CTC[i].size();j++)
			fout<<CTC[i][j]<<' ';
		fout<<"\n";
	}

	return 0;
}