Cod sursa(job #2314510)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 8 ianuarie 2019 17:03:02
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> Ad[100001];
vector <int> Ad_rev[100001];
int viz[100001];
int N,M;
vector <int> S;
void SortTop(int x)
{
    viz[x]=1;
    for(int i=0;i<Ad[x].size();++i)
        if(!viz[Ad[x][i]])SortTop(Ad[x][i]);
    S.push_back(x);
}
void Read()
{
    int x,y;
    fin>>N>>M;
    for(int i=1;i<=M;++i)
    {
        fin>>x>>y;
        Ad[x].push_back(y);
        Ad_rev[y].push_back(x);
    }
    SortTop(1);
}
void DFS(int x,bool c)
{
    viz[x]=1;
    if(c==1)fout<<x<<" ";
    for(int i=0;i<Ad_rev[x].size();++i)
        if(viz[Ad_rev[x][i]]==0)DFS(Ad_rev[x][i],c);
}
void Solve()
{
    for(int i=1;i<=N;++i)viz[i]=0;
    int nr_comp=0;
    for(int i=S.size()-1;i>=0;--i)
    {
        if(viz[S[i]]==0){DFS(S[i],0);nr_comp++;}
    }
    fout<<nr_comp<<"\n";
    for(int i=1;i<=N;++i)viz[i]=0;
    for(int i=S.size()-1;i>=0;--i)
    {
        if(viz[S[i]]==0){DFS(S[i],1);fout<<"\n";}
    }
}
int main()
{
    Read();
    Solve();
    return 0;
}