Cod sursa(job #2455127)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 10 septembrie 2019 20:30:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define NMAX 100009
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> g[NMAX];
vector<int> gt[NMAX];
vector<int>sol[NMAX];
stack<int> H;
int uz[NMAX];
int n,m,nrc,i,j;


void citire();
void dfs(int k);
void dfs1(int k);
int main()
{citire();
  for(i=1;i<=n;i++)
    if(!uz[i])
        nrc++,dfs(i);
 for(i=1;i<=n;i++)
    uz[i]=0;
 nrc=0;
 while(!H.empty())
    {
     int x1;
     x1=H.top();H.pop();//fout<<x1<<" ";
     if(!uz[x1])
        nrc++,dfs1(x1);
    }
    fout<<nrc;fout<<'\n';
  for(i=1;i<=nrc;i++)
    {for(j=0;j<sol[i].size();j++)
       fout<<sol[i][j]<<" ";
    fout<<'\n';
    }
    return 0;
}
void citire()
{int x,y;
  fin>>n>>m;
  for(int i=1;i<=m;i++)
    {
     fin>>x>>y;
     g[x].push_back(y);
     gt[y].push_back(x);

     }
}
void dfs(int k)
{
 uz[k]=nrc;
 for(int i=0;i<g[k].size();i++)
         if(!uz[g[k][i]])
            dfs(g[k][i]);
H.push(k);
}
void dfs1(int k)
{
int i;
uz[k]=nrc;
sol[nrc].push_back(k);
 for(i=0;i<gt[k].size();i++)
      if(!uz[gt[k][i]])
          dfs1(gt[k][i]);
}