Cod sursa(job #530727)

Utilizator iconiKMircea Chirea iconiK Data 8 februarie 2011 12:43:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;

struct vertex
{
	vertex()
	{
		x = y = i = m = f;
	}
	
	int x, y, i, m, f;
};

vector<vertex> G(200001);
vector<int> V(200001, 0);
vector<int> D;
stack<int> P, S; 
int idx, C = 0, N, M;

void tarjan(int i);

int main()
{
	ifstream in("ctc.in");
	ofstream out("ctc.out");
	
	in >> N >> M;
	
	for (int i = 1; i <= M; i++)
		in >> G[i].x >> G[i].y;
	
	for (int i = 1; i <= M; i++)
		if (G[i].i)
			tarjan(i);
		
	out << D.size() << '\n';
	for (int i = 0; i <= (int) D.size(); i++)
		out << G[i].x << ' ' << G[i].y;
}

void tarjan(int i)
{
	G[i].i = idx;
	G[i].m = idx;
	idx++;
	
	S.push(i);
	G[i].f = 1;
	
	int j = 1, k = 1;
	for (; j <= M; j++)
	{
		for (; k <= M; k++)
		{
			if (!G[k].i)
			{
				tarjan(k);
				G[j].m = min(G[j].m, G[k].m);
			}
			else if (G[k].f)
			{
				G[j].m = min(G[j].m, G[k].i);
			}
		}
	}
	
	if (G[j].m == G[k].m)
	{
		do
		{
			k = S.top();
			S.pop();
			D.push_back(k);
		} while (i != k);
	}
}