Cod sursa(job #1667328)

Utilizator alex.vasiuVasiu Alexandru alex.vasiu Data 28 martie 2016 20:55:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
vector <int> G[100005],G1[100005],v,rez[100005];
vector <int> marcat;
string res="";
int k;
void dfs1(int nod)
{
    marcat[nod]=1;
    for(auto p : G1[nod])
        if(!marcat[p])
        dfs1(p);
         v.push_back(nod);
}
void dfs2(int nod,int comp)
{
    marcat[nod]=comp;
    rez[comp-1].push_back(nod);
    for(auto p : G[nod])
        if(!marcat[p])
        dfs2(p,comp);
}
int main()
{
   f>>n>>m;
   marcat.resize(n+1);
   for(int i=0;i<m;i++)
   {
       int a,b;
       f>>a>>b;
       G[a].push_back(b);
       G1[b].push_back(a);
   }
   for(int i=1;i<=n;i++)
    if(!marcat[i])
      dfs1(i);
    fill(begin(marcat),end(marcat),0);
    int nr=v.size()-1;
    for(;nr>=0;nr--)
        if(!marcat[v[nr]])  {
        dfs2(v[nr],k+1);
        k++;
   }
    g<<k<<"\n";
   for(int i=0;i<k;i++)
    {
        for(auto x:rez[i])
    g<<x<<" ";

       g<<"\n";
   }
}