Cod sursa(job #2206707)

Utilizator shantih1Alex S Hill shantih1 Data 23 mai 2018 15:36:36
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

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

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

void tarjan(int x)
{
	q.push_back(x);
	low[x]=id;
	f[x]=id++;
	for(int i=0;i<vec[x].size();i++)
	{
		if(f[vec[x][i]]==0)
			tarjan(vec[x][i]);
		low[x]=min(low[x],low[vec[x][i]]);
	}
	if(low[x]==f[x])
	{
		rz++;
		while(!q.empty()&&f[q.back()]>=f[x])	
		{
			cmp[rz].push_back(q.back());
			q.pop_back();
		}
	}
}
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";
	}
}