Cod sursa(job #1449464)

Utilizator MaarcellKurt Godel Maarcell Data 9 iunie 2015 17:33:16
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

int N,M,K; vector<int> graf[100010],graft[100010],aux[100010]; bool v[100010],v2[100010],c[100100];

void dfs(int nod){
    if (v[nod] || c[nod]) return;
    v[nod]=1;

    for (int i=0; i<graf[nod].size(); i++)
        dfs(graf[nod][i]);
}

void dfs2(int nod){
    if (v2[nod] || c[nod]) return;
    v2[nod]=1;
    if (v[nod]) aux[K].push_back(nod);

    for (int i=0; i<graft[nod].size(); i++)
        dfs2(graft[nod][i]);
}

int main(){
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> N >> M;

    int i,j,x,y;
    for (i=1; i<=M; i++){
        fin >> x >> y;
        graf[x].push_back(y);
        graft[y].push_back(x);
    }

    for (i=1; i<=N; i++)
        if (!c[i]){
            memset(v,0,sizeof(v));
            memset(v2,0,sizeof(v2));
            K++;
            dfs(i);
            dfs2(i);
            for (j=0; j<aux[K].size(); j++)
                c[aux[K][j]]=1;
        }

    fout << K << "\n";
    for (i=1; i<=K; i++, fout << "\n")
        for (j=0; j<aux[i].size(); j++)
            fout << aux[i][j] << " ";

    return 0;
}