Cod sursa(job #2101285)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 7 ianuarie 2018 09:41:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define MAXN 100000

std::vector <int> G[1 + MAXN];

std::vector <int> SCC;
std::vector <std::vector<int>> M;
int pos[1 + MAXN], lowlink[1 + MAXN];
int st[1 + MAXN], last, instack[1 + MAXN];

void tarjan(int node){
    st[++last] = node;
    instack[node] = 1;
    pos[node] = lowlink[node] = last;

    for(auto y:G[node]){
        if(!pos[y])
            tarjan(y), lowlink[node] = std::min(lowlink[node], lowlink[y]);
        else if(instack[y])
            lowlink[node] = std::min(lowlink[node], lowlink[y]);
    }
    if(pos[node] == lowlink[node]){
        int x;
        SCC.clear();
        do{
            x = st[last--];
            SCC.push_back(x);
            instack[x] = 0;
        }while(x != node);
        M.push_back(SCC);
    }
}

int main(){
    FILE*fi,*fo;
    fi = fopen("ctc.in","r");
    fo = fopen("ctc.out","w");

    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    for(int i = 1; i <= m; i++){
        int x, y;
        fscanf(fi,"%d%d", &x, &y);
        G[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)
        if(!pos[i]) tarjan(i);
    fprintf(fo,"%d\n", M.size());
    for(int i = 0; i < M.size(); i++){
        for(int j = 0; j < M[i].size(); j++)
            fprintf(fo,"%d ", M[i][j]);
        fprintf(fo,"\n");
    }

    fclose(fi);
    fclose(fo);
    return 0;
}