Cod sursa(job #2928934)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 24 octombrie 2022 11:43:39
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
int low[100005], tm[100005], scc[100005], idx, compCnt;
vector<int> g[100005];
vector<vector<int> > ctc;
stack<int> stk;

void tarjan(int x) {
    stk.push(x);
    low[x] = tm[x] = ++idx;

    for(auto next: g[x]) {
        if(!tm[next]) { // next hasnt been visited yet => it is a child of x
            tarjan(next);
            low[x] = min(low[x], low[next]);
        } else if(scc[next] == 0) { // it wasnt assigned to a scc => it is an ancestor whose level may improve low[x]
            low[x] = min(low[x], tm[next]);
        }
    }

    // if we didn't find low improvements
    // pop everything from the stack and create a new scc
    if(low[x] == tm[x]) {
        compCnt ++;
        ctc.push_back({});
        while(!stk.empty()) {
            int nx = stk.top();
            stk.pop();

            ctc.back().push_back(nx);
            scc[nx] = compCnt;

            if(nx == x) break;
        }
    }
}

int main() {
	fin >> n >> m;
	while(m--) {
		int a, b;
		fin >> a >> b;
		g[a].push_back(b);
	}
	for(int i = 1; i <= n; i++)
		if(!scc[i]) tarjan(i);


	fout << ctc.size() << '\n';
	for(auto x: ctc) {
		for(auto y: x) fout << y << ' ';
		fout << '\n';
	}
}