Cod sursa(job #1909538)

Utilizator ifrimencoAlexandru Ifrimenco ifrimenco Data 7 martie 2017 13:01:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define nmax 100002
using namespace std;
vector <int> v[nmax], vt[nmax];
vector <int> postordine;
int viz[nmax];

void DFS (int x)
{
    viz[x]=1;
    vector <int> :: iterator it;
    for (it=v[x].begin();it!=v[x].end(); ++it)
        if (!viz[*it]) DFS(*it);
    postordine.push_back(x);
}
vector <int> sol[nmax];


void DFST (int x, int y)
{
    vector <int> :: iterator it;
    sol[y].push_back(x);
    viz[x]=0;
    for (it=vt[x].begin();it!=vt[x].end();++it)
        if (viz[*it]) DFST(*it,y);

}
int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
 int n, m, i, j;
 f >> n >> m;
 int x, y;
 for (i=1;i<=m; ++i)
 {
     f >> x >> y;
     v[x].push_back(y);
     vt[y].push_back(x);
 }
 for (i=1; i<=n; ++i)
    if (!viz[i]) DFS(i);
 y=0;
 vector <int> :: reverse_iterator it;

 for (it=postordine.rbegin();it!=postordine.rend();++it)
if (viz[*it]) DFST(*it,++y);
g << y << "\n";
  for (i=1; i<=y; ++i)
  {
      vector <int> :: iterator it;
      for (it=sol[i].begin();it!=sol[i].end();++it)
        g << *it << " ";
      g << "\n";
  }
    return 0;
}