Cod sursa(job #3327843)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 5 decembrie 2025 14:55:06
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define N 100005
int m, n, x, y, ind, C;
struct Node {
    vector<int> adj;
    int index;
    int low;
    int comp;
};
struct SCC {
    vector<int> a;
}a[N];
Node v[N];
stack<int> s;
void tarjan(int i) 
{
    v[i].index = ind;
    ind ++;
    v[i].low = v[i].index;
    s.push(i);
    for (auto val : v[i].adj) {
        if (v[val].index == -1) {
            tarjan(val);
            v[i].low = min(v[i].low, v[val].low);
        } else if (v[val].comp == -1) {
            v[i].low = min(v[i].low, v[val].index);
        }
    }

    if (v[i].index == v[i].low) {
        int j;
        C ++;
        do {
            j = s.top();
            s.pop();
            v[j].comp = C;
            a[C].a.push_back(j);
        } while (j != i);
    }
}
int main()
{
    fin >> n >> m;
    for (int i=1;i<=m;i++) {
        fin >> x >> y;
        v[x].adj.push_back(y);
        v[x].index = -1;
        v[x].comp = -1;
    }
    for (int i=1;i<=n;i++) {
        if (v[i].index == -1) {
            tarjan(i);
        }
    }

    fout << C << '\n';
    for (int i=1;i<=C;i++) {
        for (auto val : a[i].a) {
            fout << val << ' ';
        }
        fout << '\n';
    }

}