Cod sursa(job #2277711)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 6 noiembrie 2018 19:03:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

deque<int> St;
vector<int> ANS,ans[100010],v[100010],u[100010];
int n,m,i,j,x,y,comp[100010];
bitset<100010> viz;

void dfs(int poz)
{
    viz[poz]=1;
    for(auto it:v[poz])
        if(!viz[it])
            dfs(it);
    St.push_front(poz);
}

void dfs2(int poz,int root)
{
    viz[poz]=1;
    comp[poz]=root;
    for(auto it:u[poz])
        if(!viz[it])
            dfs2(it,root);
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        u[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    viz.reset();
    for(auto it:St)
        if(!viz[it])
            dfs2(it,it);
    for(i=1;i<=n;i++)
        ans[comp[i]].push_back(i);
    for(i=1;i<=n;i++)
        if(ans[i].size())
            ANS.push_back(i);
    g<<ANS.size()<<'\n';
    for(auto it:ANS)
    {
        for(auto that:ans[it])
            g<<that<<' ';
        g<<'\n';
    }
    return 0;
}