Cod sursa(job #2206836)

Utilizator shantih1Alex S Hill shantih1 Data 23 mai 2018 21:58:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define NMAX 100005

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,i,j,a,b,id,rz,nr,f[NMAX],low[NMAX];
bool estq[NMAX];
vector<int> vec[NMAX];
deque<int> q;
vector<int> cmp[NMAX];

void tarjan(int x)
{
	q.push_back(x);
	estq[x]=1;
	low[x]=id;
	f[x]=id++;
	for(int i=0;i<vec[x].size();i++)
	{
		if(!f[vec[x][i]])
		{
			tarjan(vec[x][i]);
			low[x]=min(low[x],low[vec[x][i]]);
		}
		else if(estq[vec[x][i]])	low[x]=min(low[x],f[vec[x][i]]);
	}
	if(low[x]==f[x])
	{
		rz++;
		do
		{
			nr=q.back();
			estq[nr]=0;
			cmp[rz].push_back(nr);
			q.pop_back();
		}while(nr!=x);
	}
}
int main() {
	
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b;
		vec[a].push_back(b);
	}
	id=1;
	for(i=1;i<=n;i++)
		if(f[i]==0)
		{
			tarjan(i);
		}
	fout<<rz<<"\n";
	for(i=1;i<=rz;i++)
	{
		for(j=0;j<cmp[i].size();j++)
			fout<<cmp[i][j]<<" ";
		fout<<"\n";
	}
}