Cod sursa(job #530732)

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

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

vector<vertex> G(200001);
vector<int> V(200001, 0);
vector<int> D;
stack<int> 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 << C << '\n';
	for (int i = 0; i <= (int) D.size(); i++)
		out << G[i].x << ' ' << G[i].y << '\n';
}

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