Cod sursa(job #2656160)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 6 octombrie 2020 21:55:38
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <cstdio>
#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() {
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	int n, m, x, y;
	scanf("%d%d", &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) {
		scanf("%d%d", &x, &y);
		arcs[x].push_back(y);
	}

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

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

	return 0;
}