Cod sursa(job #2073329)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 22 noiembrie 2017 22:51:54
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

int nxt;
vector <int> adj[100005];
vector < vector<int> > cmp;
vector <int> ax;
int disc[100005], low[100005];
bool viz[100005];
bool in_s[100005];
stack <int> s;

void dfs(int node){
    ++nxt;
    disc[node] = low[node] = nxt;
    viz[node] = 1;
    in_s[node] = 1;
    s.push(node);
    for(auto it : adj[node]){
        if(viz[it] == 0){
            dfs(it);
        }
        low[node] = min(low[node], low[it]);
    }
    if(disc[node] == low[node]){
        int u;
        ax.clear();
        do{
            u = s.top();
            in_s[u] = 0;
            s.pop();
            ax.push_back(u);
        }while(u != node);
        cmp.push_back(ax);
    }
}

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n,m,i,x,y;
    fin>>n>>m;
    for(i = 1;i <= m;i++){
        fin>>x>>y;
        adj[x].push_back(y);
    }
    for(i = 1;i <= n;i++){
        if(viz[i] == 0){
            dfs(i);
        }
    }
    fout<<cmp.size()<<'\n';
    for(auto v : cmp){
        for(auto it : v){
            fout<<it<<' ';
        }
        fout<<'\n';
    }
}