Cod sursa(job #3136231)

Utilizator DavidLDavid Lauran DavidL Data 5 iunie 2023 18:03:29
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int NMAX = 1e5 + 5;

int n, m;
vector<int> G[NMAX];
int height[NMAX], highestJump[NMAX];
int noComp, compOfVertex[NMAX];
stack<int> s;  // when in dfs(x), it contains those vertices in its subtree which aren't in a SCC yet
bool isOnStack[NMAX];

void dfs(int vertex) {
    highestJump[vertex] = height[vertex];
    s.push(vertex);
    isOnStack[vertex] = true;

    for (auto neighbor: G[vertex])
        if (height[neighbor]) { // visited 
            highestJump[vertex] = min(highestJump[vertex], highestJump[neighbor]);
        }
        else  {// tree vertex 
            height[neighbor] = height[vertex] + 1;
            dfs(neighbor);
            highestJump[vertex] = min(highestJump[vertex], highestJump[neighbor]);
        }

    if (highestJump[vertex] == height[vertex]) {
        // root of SCC
        noComp++;
        compOfVertex[vertex] = noComp;
        while (s.top() != vertex) {
            int x = s.top();
            s.pop();
            isOnStack[x] = false;
            compOfVertex[x] = noComp;
        }
        s.pop();
        isOnStack[vertex] = false;
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; fin >> u >> v;
        G[u].push_back(v);
    }

    for (int i = 1; i <= n; i++)
        if (height[i] == 0) {
            height[i] = 1;
            dfs(i);
        }

    // for (int i = 1; i <= n; i++)
    //     cout << highestJump[i] << " ";

    vector<vector<int>> verticesInComp(noComp + 1);
    for (int i = 1; i <= n; i++)
        verticesInComp[compOfVertex[i]].push_back(i);

    fout << noComp << "\n";
    for (int i = 1; i <= noComp; i++) {
        for (int x : verticesInComp[i])
            fout << x << " ";
        fout << "\n";
    }

    return 0;
}