Cod sursa(job #681746)

Utilizator adrian401NAN NAN adrian401 Data 17 februarie 2012 18:28:04
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
//
//  main.cpp
//  ctc3
//
//  Created by Nenu Adrian on 2/17/12.
//  Copyright 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> G[100100],GT[100100],A,S[100100];
int j,m,n,sol,nr,t[100100],viz[100100];

void df(int nod){
    viz[nod]=1;
    int i;
    for (i=0; i < G[nod].size();i++){
        if(!viz[G[nod][i]])
            df(G[nod][i]);
    }
    t[nod]=++nr;
    
}

void dff(int nod){
    viz[nod]=1;
    S[sol].push_back(nod);
    int i;
    for (i=0; i < GT[nod].size();i++){
        if(!viz[GT[nod][i]])
            dff(GT[nod][i]);
    }
   
    
}

bool cmp(int a, int b){
    return (t[a]>t[b]);
}

int main(){
    int i,x,y,n,m;
    ifstream f("ctc.in");
	ofstream g("ctc.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    
    for(i=1;i<=n;i++)
        if(!viz[i])
            df(i);
    for(i=1;i<=n;i++){
        viz[i]=0;
        A.push_back(i);
    }
    sort(A.begin(), A.end(), cmp);
    for(i=0;i<n;i++)
        if(!viz[A[i]])
        {
            sol++;
            dff(A[i]);
        }
    g<<sol<<endl;
    for(i=1;i<=sol;i++){
        for(j=0;j<S[i].size();j++)
            g<<S[i][j]<<" ";
            
        g<<endl;}
}