Cod sursa(job #2568063)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 3 martie 2020 20:39:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define Nmax 100005
#define INF 0x3f3f3f3f
#define MOD 1999999973

using namespace std;

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

int n, m;
vector <int> v[Nmax], in[Nmax];
vector <int> sol[Nmax];
bool u1[Nmax], u2[Nmax];
int st[Nmax], top, ctc;

void dfs1(int x)
{
    u1[x]=1;
    for (auto y:v[x])
    {
        if (u1[y] == 1) continue;
        dfs1(y);
    }
    st[++top]=x;
}

void dfs2(int x)
{
    u2[x]=1;
    for (auto y:in[x])
    {
        if (u2[y] == 1) continue;
        dfs2(y);
    }
    sol[ctc].push_back(x);
}

int main()
{
    f >> n >> m;
    for (int i = 1, x, y; i <= m; i++)
    {
        f >> x >> y;
        v[x].push_back(y);
        in[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
        if (u1[i] == 0) dfs1(i);


    while (top > 0)
    {
        if (u2[st[top]] == 1) top--;
        else
        {
            dfs2(st[top]);
            top--;
            ctc++;
        }
    }

    g << ctc << '\n';
    for (int i = 0; i < ctc; i++)
    {
        for (auto y:sol[i])
            g << y << ' ';
        g << '\n';
    }


    return 0;
}