Cod sursa(job #3278786)

Utilizator alexlazuLazureanu Alexandru Ioan alexlazu Data 20 februarie 2025 19:07:40
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define cin in
#define cout out

const int N = 2e5 + 1;

vector<int> v[N] , g[N];

int added[N], eliminated[N];

void dfs(int nod)
{
    added[nod] = 1;
    for (auto i : v[nod])
    {
        if (added[i] == 0)
        {
            dfs(i);
        }
    }
}

void dfs_minus(int nod)
{
    eliminated[nod] = 1;
    for (auto i : g[nod])
    {
        if (eliminated[i] == 0)
            dfs_minus(i);
    }
}

signed main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1,a,b; i <= m; i++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        g[b].push_back(a);
    }
    int sol = 0;
    for (int i = 1; i <= n; i++)
    {
        if (added[i] == 0 || eliminated[i] == 0)
        {
            sol++;
            dfs(i);
            dfs_minus(i);
            for (int j = 1; j <= n; j++)
            {
                //cout << ">>> " << added[j] << ' ' << eliminated[j] << '\n';
                if (added[j] == 1 && eliminated[j] == 1)
                {
                    //cout << j << ' ';
                    added[j] = eliminated[j] = 2;
                }
            }
            //cout << '\n';
        }
    }
    cout << sol << '\n';
    for (int i = 0; i <= n; i++)
        added[i] = eliminated[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (added[i] == 0 || eliminated[i] == 0)
        {
            dfs(i);
            dfs_minus(i);
            for (int j = 1; j <= n; j++)
            {
                //cout << ">>> " << added[j] << ' ' << eliminated[j] << '\n';
                if (added[j] == 1 && eliminated[j] == 1)
                {
                    cout << j << ' ';
                    added[j] = eliminated[j] = 2;
                }
            }
            cout << '\n';
        }
    }
}