Cod sursa(job #1368218)

Utilizator traian.vidrascutraian vidrascu traian.vidrascu Data 2 martie 2015 15:13:47
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector <int> gr[100005],gr2[100005],v[100005];
int n,m,viz[100005],viz2[100005],d[100005],l;
bool v3[100005];
void dfs(int p)
{
	int i;
	viz[p]=1;
	d[p]++;
	for(i=0;i<gr[p].size();i++)
	{
		if(viz[gr[p][i]]==0 && v3[gr[p][i]]==0)
			dfs(gr[p][i]);
	}
}
void dfs2(int p)
{
	int i;
	viz2[p]=1;
	d[p]--;
	for(i=0;i<gr2[p].size();i++)
	{
		if(viz2[gr2[p][i]]==0 && v3[gr2[p][i]]==0)
			dfs2(gr2[p][i]);
	}
}
int main()
{
	int i,j,x,y;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		gr[x].push_back(y);
		gr2[y].push_back(x);
	}
	for(i=1;i<=n;i++)
	{
		if(viz[i]==0 && v3[i]==0)
		{
			dfs(i);
			dfs2(i);
			l++;
			for(j=1;j<=n;j++)
			{
					if(d[j]==0 && viz[j]==1 && viz2[j]==1)
					{
						v3[j]=1;
						v[l].push_back(j);
					}
					d[j]=0;
					viz[j]=0;
					viz2[j]=0;
			}
				
		}
	}
	g<<l;
	for(i=1;i<=l;i++)
		{
			g<<"\n";
			for(j=0;j<v[i].size();j++)
			g<<v[i][j]<<" ";
		}
}