Cod sursa(job #2656162)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 6 octombrie 2020 22:02:03
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

vector<vector<int>> arcs;
vector<int> lowlink, index, components;
vector<bool> onStack;

stack<int> st;

int componentsNo, currentComp;

int min(int x, int y) {
	return x<y? x:y;
}

void strongConnect(int x) {
	st.push(x);

	++currentComp;
	lowlink[x] = currentComp;
	index[x] = currentComp;
	onStack[x] = true;

	for(int i=0; i<arcs[x].size(); ++i) {
        int nextNode = arcs[x][i];
		if (! index[nextNode]) {
			strongConnect(nextNode);
			lowlink[x] = min(lowlink[x], lowlink[nextNode]);
		} else
			if (onStack[nextNode])
				lowlink[x] = min(lowlink[x], index[nextNode]);
	}

	if (lowlink[x] == index[x]) {
        ++componentsNo;

        int n;
		do {
		    n = st.top();
			onStack[st.top()] = false;
			st.pop();

			components[n] = componentsNo;
		} while (n != x);
	}
}


int main() {
    ifstream in("ctc.in");
    ofstream out("ctc.out");
	int n, m, x, y;
	in >> n >> m;

	arcs.resize(n+2);
	lowlink.resize(n+2, 0);
	index.resize(n+2, 0);
	components.resize(n+2, 0);
	onStack.resize(n+2, false);

	for(int i=0; i<m; ++i) {
		in >> x >> y;
		arcs[x].push_back(y);
	}

	for(int i=1; i<=n; ++i)
		if (index[i] == 0)
			strongConnect(i);

	out << componentsNo << "\n";
	for(int i=1; i<=componentsNo; ++i) {
		for(int j=1; j<=n; ++j)
			if (components[j] == i)
				out << j << " ";
		out << "\n";
	}

	return 0;
}