Cod sursa(job #2383674)

Utilizator DovlecelBostan Andrei Dovlecel Data 19 martie 2019 18:55:41
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N=100002;
int n,m,cnt,cnt2,srt[N];
bool viz[N],vizz[N];
vector<int>a[N],b[N],sol[N];

void dfs(int x)
{
    int y;
    viz[x]=true;
    for(unsigned i=0;i<a[x].size();i++)
    {
        y=a[x][i];
        if(!viz[y])
            dfs(y);
    }
    srt[++cnt]=x;
}
void dfs2(int x)
{
    int y;
    vizz[x]=true;
    sol[cnt2].push_back(x);
    for(unsigned i=0;i<b[x].size();i++)
    {
        y=b[x][i];
        if(!vizz[y])
            dfs2(y);
    }
}
int main()
{
    int x,y;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    for(int i=1;i<=n;i++)
        if(!vizz[i])
        {
            cnt2++;
            dfs2(i);
        }
    out<<cnt2<<'\n';
    for(int i=1;i<=cnt2;i++)
    {
        for(unsigned j=0;j<sol[i].size();j++)
            out<<sol[i][j]<<' ';
        out<<'\n';
    }
    return 0;
}