Cod sursa(job #2159494)

Utilizator OpportunityVlad Negura Opportunity Data 10 martie 2018 23:14:45
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("ctc.in");
ofstream fo("ctc.out");

int n,m,x,y,idx[100001],idxc=1,in[100001],low[100001];
vector<int> g[100001];
vector<vector<int>> scc;
stack<int> s;

void tarjan(int v) {
    idx[v] = low[v] = idxc;
    idxc++;
    s.push(v);
    in[v] = 1;

    for (auto &u:g[v]) {
        if (idx[u] == 0){
            tarjan(u);
            low[v] = min(low[v], low[u]);
        } else if (in[u]) {
            low[v] = min(low[v], idx[u]);
        }
    }

    if (low[v] == idx[v]) {
        vector<int> comp;
        int u;
        do {
            u = s.top();
            in[u] = 0;
            s.pop();
            comp.push_back(u);
        } while(u != v);
        scc.push_back(comp);
    }
}


int main() {
    fi >> n >> m;

    while (m--) {
        fi >> x >> y;
        g[x].push_back(y);
    }

    for (int i=1; i<=n; i++) {
        if (!idx[i]) tarjan(i);
    }

    fo << scc.size() << endl;
    for (auto x:scc) {
        for (auto y:x) fo << y << ' ';
        fo << endl;
    }

    return 0;
}