Cod sursa(job #1431202)

Utilizator muraru_georgeMuraru George Cristian 323CB muraru_george Data 9 mai 2015 02:14:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <stdio.h>


#define MAX 100000

using namespace std;

vector <int> adj[MAX], idx, lowlink, in_stack;
stack <int> st;
int t, component;
vector <vector<int> > components;


int min(int a, int b) {
	return (a > b)? b : a;
}

void tarjan(int n) {
	idx[n] = lowlink[n] = t;
	t++;

	st.push(n); in_stack[n] = 1;
	for (vector<int>::iterator it = adj[n].begin(); it != adj[n].end(); ++it)
		if (idx[*it] == -1) {
			tarjan(*it);
			lowlink[n] = min(lowlink[n], lowlink[*it]);
		}
		else if (in_stack[*it]) {
			lowlink[n] = min(lowlink[n], idx[*it]);
		}

	if (idx[n] == lowlink[n]) {
		int node;
		do {
			node = st.top();
			components[component].push_back(node);
			st.pop(); in_stack[node] = 0;
		} while (node != n);
		component++;
	}

}


int main() {

	freopen ("ctc.in", "rt", stdin);
	freopen ("ctc.out", "wt", stdout);

	int n, m;

	cin >> n >> m;
	int n1, n2;

	idx.resize(n+1);
	idx.assign(n+1, -1);
	lowlink.resize(n+1);
	lowlink.assign(n+1, -1);

	in_stack.resize(n+1);
	in_stack.assign(n+1, 0);
	
	components.resize(n);
	for (int i = 0; i < m; ++i) {
		cin >> n1 >> n2;
		adj[n1].push_back(n2);
	}

	for (int i = 1; i <= n; ++i)
		if (idx[i] == -1)
			tarjan(i);

	cout << component << "\n";
	for (unsigned int i = 0; i < components.size(); ++i) {
		for (unsigned int j = 0; j < components[i].size(); ++j)
			cout << components[i][j] << " ";
		cout << "\n";
	}
}