Cod sursa(job #2076023)

Utilizator Horia14Horia Banciu Horia14 Data 25 noiembrie 2017 23:14:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<cstdio>
#include<vector>
#include<stack>
#define MAX_N 100000
using namespace std;

vector<int>G[MAX_N+1], Gt[MAX_N+1], ctc[MAX_N+1];
stack<int>st;
bool used[MAX_N+1];
int n, m, nrctc;

void DFS(int node) {
    used[node] = true;
    vector<int>::iterator it;
    for(it = G[node].begin(); it != G[node].end(); it++)
        if(!used[*it])
            DFS(*it);
    st.push(node);
}

void DFSmaster(int n) {
    for(int i = 1; i <= n; i++)
        if(!used[i])
            DFS(i);
}

void DFSreverseGraph(int node) {
    used[node] = true;
    ctc[nrctc].push_back(node);
    vector<int>::iterator it;
    for(it = Gt[node].begin(); it != Gt[node].end(); it++)
        if(!used[*it])
            DFSreverseGraph(*it);
}

void Kosaraju() {
    for(int i = 1; i <= n; i++)
        used[i] = false;
    while(!st.empty()) {
        int node = st.top();
        st.pop();
        if(!used[node]) {
            DFSreverseGraph(node);
            nrctc++;
        }
    }
}

int main() {
    int x, y;
    vector<int>::iterator it;
    FILE *fin, *fout;
    fin = fopen("ctc.in","r");
    fout = fopen("ctc.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(int i = 0; i < m; i++) {
        fscanf(fin,"%d%d",&x,&y);
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    DFSmaster(n);
    Kosaraju();
    fprintf(fout,"%d\n",nrctc);
    for(int i = 0; i < nrctc; i++) {
        for(it = ctc[i].begin(); it != ctc[i].end(); it++)
            fprintf(fout,"%d ",*it);
        fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}