Cod sursa(job #1667306)

Utilizator alex.vasiuVasiu Alexandru alex.vasiu Data 28 martie 2016 20:37:32
Problema Componente tare conexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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;
vector <int> marcat;
string res="";
int k;
void dfs1(int nod)
{
    marcat[nod]=1;
    v.push_back(nod);
    for(auto p : G1[nod])
        if(!marcat[p])
        dfs1(p);
}
void dfs2(int nod)
{
    marcat[nod]=0;
    int a=nod;
    while(a)
        res+=('0'+a%10),a/=10;
        res+=' ';
    for(auto p : G[nod])
        if(marcat[p])
        dfs2(p);
}
int main()
{
   f>>n>>m;
   //g<<"\n";
   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);
    int nr=v.size()-1;
    for(;nr>=0;nr--)
        if(marcat[v[nr]])
    {
        dfs2(v[nr]);
        k++;
       res+='\n';
   }
    g<<k<<"\n";
    g<<res;
}