Cod sursa(job #1363671)

Utilizator LurchssLaurentiu Duma Lurchss Data 27 februarie 2015 09:51:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

#define nmax 100005
using namespace std;
vector<int> v[nmax],g[nmax];
vector<int> ctc[nmax];
stack<int> s;
bitset<nmax> viz;
int n,m,nr_ctc;
void read()
{
   scanf("%d %d",&n,&m);
   int x,y;
   for(int i=1;i<=m;i++)
      {scanf("%d %d",&x,&y);
      v[x].push_back(y);
      g[y].push_back(x);}
}

void dfs(int x)
{
   viz[x]=1;
   for(int i=0;i<v[x].size();i++)
      if(viz[v[x][i]]==0)
         dfs(v[x][i]);
   s.push(x);
}
void sort_top1()
{
   for(int i=1;i<=n;i++)
      if(viz[i]==0)
         dfs(i);
}

void dfs2(int x)
{
   viz[x]=1;
   ctc[nr_ctc].push_back(x);
   for(int i=0;i<g[x].size();i++)
      if(viz[g[x][i]]==0)
         dfs2(g[x][i]);}

void sort_top2()
{
   viz=0;
   while(!s.empty())
   {
      if(viz[s.top()]==0)
         {
            nr_ctc++;
            dfs2(s.top());
          }
      s.pop();
   }
   printf("%d\n",nr_ctc);
   for(int i=1;i<=nr_ctc;i++,printf("\n"))
      for(int j=0;j<ctc[i].size();j++)
            printf("%d ",ctc[i][j]);

}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    read();
    sort_top1();
    sort_top2();
    return 0;
}