Cod sursa(job #1717660)

Utilizator lflorin29Florin Laiu lflorin29 Data 15 iunie 2016 14:38:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;

int dftime, n, m, tin[MAXN + 2], low[MAXN + 2], in_stk[MAXN + 2];
vector<int>comp;
vector<int>adj[MAXN + 2];
vector<vector<int>>allcomps;
stack<int>st;
bool vis[MAXN + 2];

void read() {
    ifstream f("ctc.in");

    f >> n >> m;

    for(int i = 1, x, y; i <= m; ++i) {
        f >> x >> y;
        adj[x].push_back(y);
    }

}

void get_scc(int nod) {
    comp = vector<int>();
    int curr;

    do {
       curr = st.top(), in_stk[curr] = false;
       comp.push_back(curr);
       st.pop();
    }
    while(!st.empty() && curr != nod);

    allcomps.push_back(comp);

}

void dfs(int nod) {
    tin[nod] = low[nod] = ++dftime;
    in_stk[nod] = true;
    vis[nod] = true;
    st.push(nod);

    for(auto current: adj[nod]) {

       if(!vis[current]) {
         dfs(current);
         low[nod] = min(low[nod], low[current]);
       }

       else if(in_stk[current])
           low[nod] = min(low[nod], tin[current]);
    }

    if(low[nod] == tin[nod])
       get_scc(nod);
}

void solve() {
    for(int i = 1; i <= n; ++i)
       if(!vis[i])
         dfs(i);

    ofstream g("ctc.out");

    g << allcomps.size() << '\n';
    for(auto& current: allcomps) {
        for(auto &iter: current)
           g << iter << ' ';
        g << '\n';
    }
}

int main() {
    read();
    solve();
    return 0;
}