Cod sursa(job #1410372)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 31 martie 2015 00:32:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

vector<vector<int>> edges;

vector<bool> visited,on_stack;
vector<int> index, lowlink;
vector<vector<int>> components;
stack<int> nodes_visited;
int c_index = 0;

void strongconnect(int v) {
	visited[v] = true;
	on_stack[v] = true;
	nodes_visited.push(v);
	index[v] = c_index;
	lowlink[v] = c_index++;

	for(int w:edges[v]) {
		if(!visited[w]) {
			strongconnect(w);
			lowlink[v] = min(lowlink[v],lowlink[w]);
		}
		else if(on_stack[w]) {
			lowlink[v] = min(lowlink[v],index[w]);
		}
	}
	if(index[v] == lowlink[v]) {
		components.resize(components.size()+1);
		int w;
		do {
			w = nodes_visited.top();
			nodes_visited.pop();
			on_stack[w] = false;
			components.back().push_back(w);
		} while(w != v);
	}
}

int main() {
	unsigned n,m;
	in >> n >> m;
	edges.resize(n+1);
	visited.resize(n+1);
	on_stack.resize(n+1);
	index.resize(n+1);
	lowlink.resize(n+1);

	for(int i = 0; i < m; ++i) {
		int a,b;
		in >> a >> b;
		edges[a].push_back(b);
	}

	for(int i = 1; i <= n; ++i) {
		if(!visited[i])
			strongconnect(i);
	}

	out << components.size() << '\n';

	for(auto comp:components) {
		for(int node:comp) {
			out << node << ' ';
		}
		out << '\n';
	}

	return 0;
}