Cod sursa(job #2168952)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 14 martie 2018 12:54:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100005;
int dep[N], low[N], st[N], depth, nrCTC, stSize;
bool inStack[N];
vector <int> v[N], l[N];
void pushStack(int node){
    st[++stSize] = node;
    inStack[node] = true;
}
void newCTC(int ns){
    nrCTC++;
    do{
        l[nrCTC].push_back(st[stSize]);
        inStack[st[stSize]] = false;
    }while(st[stSize--] != ns);
}
void tarjan(int ns){
    int sz = v[ns].size(), nbr;
    low[ns] = dep[ns] = ++depth;
    pushStack(ns);
    for(int i=0;i<sz;i++){
        nbr = v[ns][i];
        if(dep[nbr] == 0){
            tarjan(nbr);
            if(low[ns] > low[nbr])
                low[ns] = low[nbr];
        }
        else if(inStack[nbr] && low[ns] > low[nbr])
            low[ns] = low[nbr];
    }
    if(low[ns] == dep[ns])
        newCTC(ns);
}
void print(){
    int sz;
    out<<nrCTC<<"\n";
    for(int i=1;i<=nrCTC;i++){
        sz = l[i].size();
        for(int j=0;j<sz;j++)
            out<<l[i][j]<<" ";
        out<<"\n";
    }
}
int main()
{
    int n, m, x, y;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y;
        v[x].push_back(y);
    }
    in.close();
    for(int i=1;i<=n;i++)
        if(dep[i] == 0)
            tarjan(i);
    print();
    out.close();
    return 0;
}