Cod sursa(job #1216171)

Utilizator rangerChihai Mihai ranger Data 3 august 2014 15:59:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int NMAX = 100010;
vector <int> g[NMAX], gr[NMAX], Component, order, Components[NMAX];
int n,m,i,x,y,V[NMAX], cp=0;

void  df1(int x)
{
   V[x]=1;
   int i;
   for (i=0;i<g[x].size();i++)
        if (!V[ g[x][i] ])
           df1(g[x][i]);
   order.push_back(x);
}

void df2(int x)
{
    V[x]=1;
    int i;
    Component.push_back(x);
    for (i=0;i<gr[x].size();i++)
     if (!V[ gr[x][i] ])
      df2(gr[x][i]);

}

int main()
{
    cin>>n>>m;
    while (m--)
    {
        cin>>x>>y;
        g[x].push_back(y);
        gr[y].push_back(x);
    }
    for (int i=1;i<=n;i++)
        if (!V[i]) df1(i);
    memset(V,0,sizeof V);
    for (int i=n;i>0;i--)
        if (!V[order[i-1]])
    {
        df2(order[i-1]);
        ++cp;
        for (int j=0;j<Component.size();j++) Components[cp].push_back(Component[j]);
        Component.clear();
    }
    cout<<cp<<"\n";
    for (int i=1;i<=cp;i++)
    {
        for (int j=0; j<Components[i].size();j++) cout<<Components[i][j]<<" ";
        cout<<"\n";
    }
}