Cod sursa(job #2412275)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 21 aprilie 2019 21:47:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 100000

int n, m;

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

std::vector <int> emptyVec;
std::vector <std::vector <int>> M;
int top[1 + MAXN], last;
bool seen[1 + MAXN];

void sortTop(int node){
    seen[node] = 1;
    for(auto y: G[node])
        if(!seen[y]) sortTop(y);
    top[++last] = node;
}
void dfs(int node){
    seen[node] = 1;
    M.back().push_back(node);
    for(auto y: invG[node])
        if(!seen[y]) dfs(y);
}

void Kosaraju(){
    for(int i = 1; i <= n; i++)
        if(!seen[i]) sortTop(i);
    memset(seen, 0, sizeof(seen));

    for(int i = n; i >= 1; i--)
        if(!seen[top[i]]){
            M.push_back(emptyVec);
            dfs(top[i]);
        }
}

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

    fscanf(fi,"%d%d", &n, &m);

    int i, x, y, j;
    for(i = 0; i < m; i++){
        fscanf(fi,"%d%d",&x, &y);
        G[x].push_back(y);
        invG[y].push_back(x);
    }

    Kosaraju();

    fprintf(fo,"%d\n", M.size());
    for(auto y: M){
        for(auto z: y)
            fprintf(fo,"%d ", z);
        fprintf(fo,"\n");
    }
    return 0;
}