Cod sursa(job #3278735)

Utilizator alexlazuLazureanu Alexandru Ioan alexlazu Data 20 februarie 2025 17:34:18
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <vector>
#include <map>

using namespace std;

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);
    }
    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';
        }
    }
}