Cod sursa(job #1609794)

Utilizator ArkinyStoica Alex Arkiny Data 23 februarie 2016 00:13:40
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;

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

vector<int> s;

vector<int> L1[100010];
vector<int> L2[100010];

bitset<100010> v;

void DFS1(int x)
{
	v[x] = 1;
	for (int i = 0;i < L1[x].size();++i)
		if (v[L1[x][i]] == 0)
			DFS1(L1[x][i]);
	s.push_back(x);

}
void DFS2(int x)
{
	v[x] = 1;
	for (int i = 0;i < L2[x].size();++i)
		if (v[L2[x][i]] == 0)
			DFS2(L2[x][i]);

}

int main()
{
	int N,M;

	in >> N >> M;
	for (int i = 1;i <= M;++i)
	{
		int x, y;
		in >> x >> y;
		L1[x].push_back(y);
		L2[y].push_back(x);
	}
	for (int i = 1;i <= N;++i)
	{
		if (v[i] == 0)
			DFS1(i);
	}
	v.reset();
	for (int i = N-1;i >=0;--i)
	{
		if (v[s[i]] == 0)
		{
			out << '\n';
			DFS2(s[i]);
			out << s[i]<<" ";
		}
		else
			out << s[i]<<" ";
	}
	return 0;
}