Cod sursa(job #559167)

Utilizator sodamngoodSo Damn Good sodamngood Data 17 martie 2011 17:19:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define maxn 100010

int N, M, nr, fin;
int viz[maxn], timp[maxn];
vector<int> G[maxn], Gt[maxn], CC[maxn];

void DFS(int nod) {
    viz[nod] = 1;
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if(!viz[(*it)]) DFS((*it));
    }

    timp[ ++fin ] = nod;
}

void DFSt(int nod) {
    viz[nod] = 1;
    CC[nr].push_back(nod);
    for(vector<int>::iterator it=Gt[nod].begin(); it!=Gt[nod].end(); it++) {
         if(!viz[(*it)]) DFSt((*it));
    }
}

int main() {
    FILE *f1=fopen("ctc.in", "r"), *f2=fopen("ctc.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d %d\n", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d\n", &p, &q);
         G[p].push_back(q);
         Gt[q].push_back(p);
    }

    for(i=1; i<=N; i++) {
         if(!viz[i]) {
              DFS(i);
         }
    }

    memset(viz, 0, sizeof(viz));
    for(i=N; i>=1; i--) {
         if(!viz[ timp[i] ]) {
              nr ++;
              DFSt( timp[i] );
         }
    }

    fprintf(f2, "%d\n", nr);
    for(i=1; i<=nr; i++) {
         for(j=0; j<CC[i].size(); j++) {
              fprintf(f2, "%d ", CC[i][j]);
         }
         fprintf(f2, "\n");
    }

    fclose(f1); fclose(f2);
    return 0;
}