Cod sursa(job #2669121)

Utilizator sygAndreiIonitaIonita Andrei sygAndreiIonita Data 6 noiembrie 2020 09:19:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

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

int n,m,cnt;
bool ok[100001];
vector <int> dir[100001],inv[100001],v[200001];
deque <int> d;

void dfs(int x)
{
    ok[x]=1;
    for (int i=0;i<dir[x].size();i++)
    {
        if (!ok[dir[x][i]])
            dfs(dir[x][i]),d.push_front(dir[x][i]);
    }
}

void dfs2(int x)
{
    ok[x]=1;
    for (int i=0;i<inv[x].size();i++)
    {
        if (!ok[inv[x][i]])
            dfs2(inv[x][i]),v[cnt].push_back(inv[x][i]);
    }
}

int main()
{
    int a,b;
    in>>n>>m;
    for (int i=1;i<=m;i++) // creez listele de adiacenta a grafului G si a lui G transpus
        in>>a>>b,dir[a].push_back(b),inv[b].push_back(a);
    //Kosaraju
    for (int i=1;i<=n;i++) //creez stiva din care vom mai face un dfs
    {
        if (!ok[i])
            dfs(i),d.push_front(i);
    }
    for (int i=1;i<=n;i++)
        ok[i]=0;
    for (int i : d) // de completat al doilea dfs, din stiva, al grafului G transpus
    {
        if (!ok[i])
        {
            cnt++;
            dfs2(i);
            v[cnt].push_back(i);
        }
    }
    out<<cnt<<'\n';
    for (int i=1;i<=cnt;i++)
    {
        for (int j=0;j<v[i].size();j++)
            out<<v[i][j]<<" ";
        out<<'\n';
    }
    return 0;
}