Cod sursa(job #968109)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 1 iulie 2013 20:04:54
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

#define LE 100666
#define pb push_back
#define x first
#define y second

vector<int> H[LE],graf_2[LE],result[LE];
int K,level[LE],max_up[LE];
bool viz[LE];

void dfs(int nod) {
    int N=H[nod].size(),i;
    max_up[nod]=level[nod];

    for(i=0; i<N; ++i) {
        if (level[H[nod][i]]==0) {
            level[H[nod][i]]=level[nod]+1;
            dfs(H[nod][i]);
            if (max_up[H[nod][i]]<=level[nod]) {
                graf_2[nod].pb(H[nod][i]);
                graf_2[H[nod][i]].pb(nod);
            }
        }
        max_up[nod]=min(max_up[nod],level[H[nod][i]]);
        max_up[nod]=min(max_up[nod],max_up[H[nod][i]]);
    }
}

void dfs_2(int nod) {
    viz[nod]=true;
    int N=graf_2[nod].size(),i;
    result[K].pb(nod);
    for(i=0; i<N; ++i)
        if (viz[graf_2[nod][i]]==false)
            dfs_2(graf_2[nod][i]);
}

int main() {
    int n,m,i,xx,yy;

    f>>n>>m;
    for(i=1; i<=m; ++i) {
        f>>xx>>yy;
        H[xx].pb(yy);
    }

    for(i=1; i<=n; ++i)
        if (level[i]==0) {
            level[i]=1;
            dfs(i);
        }

       for(i=1; i<=n; ++i)
           if (viz[i]==false) {
               ++K;
               dfs_2(i);
           }


   g<<K<<'\n';

    for(i=1; i<=K; ++i,g<<'\n') {
        int N=result[i].size(),j;
        for(j=0; j<N; ++j)
            g<<result[i][j]<<" ";
    }

    f.close();
    g.close();
    return 0;
}