Cod sursa(job #1605167)

Utilizator RadduFMI Dinu Radu Raddu Data 18 februarie 2016 20:06:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[100005],c[100005],vt[100005];
queue <int> q;
int n,m,k,a[100005],nc,use[100005];

void DFS(int x)
{ int i;
   use[x]=1;
   for(i=0;i<v[x].size();i++)
    if (!use[v[x][i]]) DFS(v[x][i]);
   k++; a[k]=x;
}

void BFS2(int x)
{ int i;
   q.push(x);
    use[x]=1;
    c[nc].push_back(x);
   while(!q.empty())
   { x=q.front(); q.pop();

      for(i=0;i<vt[x].size();i++)
      if (!use[vt[x][i]])
      {q.push(vt[x][i]);
       c[nc].push_back(vt[x][i]);
       use[vt[x][i]]=1;
      }
   }
}

int main()
{ int i,j,x,y;
    f>>n>>m;
    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 (!use[i]) DFS(i);

    memset(use,0,sizeof(use));



    for(i=k;i>=1;i--)
    if (!use[a[i]]) {nc++; BFS2(a[i]); }

   g<<nc<<"\n";
    for(i=1;i<=nc;i++)
    {for(j=0;j<c[i].size();j++)
      g<<c[i][j]<<" ";
     g<<"\n";
    }

    return 0;
}