Cod sursa(job #3373698)

Utilizator srares2006Samoila Rares srares2006 Data 7 noiembrie 2026 16:53:05
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("pamant.in");
ofstream fout("pamant.out");

const int NMAX = 100001;

vector<int> vecini[NMAX];
int tin[NMAX]; // ordinea in care dfs descopera nodurile
int low[NMAX]; // cel mai mic tin la care poate ajunge ramura nodului
bool critic[NMAX]; // retinem daca un nod este punct critic
int timp; // numarul de noduri descoperite pana acum

void dfs(int u, int parinte)
{
    
    timp++;
    tin[u] = timp;// tocmai l-am descoperit pe u

    
    low[u] = tin[u];// la inceput stim doar ca ramura lui u poate ajunge la u

    int copii = 0; // cati copii are u in arborele dfs

    for (int v : vecini[u])
    {
        if (v == parinte)
            continue;

        if (tin[v] == 0)
        {
            copii++;
            dfs(v, u);// v este nevizitat, deci devine un copil al lui u
            low[u] = min(low[u], low[v]);// am terminat ramura lui v si stim cat de sus poate ajunge

            // daca ramura lui v nu poate ajunge mai sus de u ea se desprinde cand il scoatem pe u
            if (parinte != 0 && low[v] >= tin[u])
                critic[u] = true;
        }
        else
        {
            // o muchie spre un stramos ne poate duce la un tin mai mic
            low[u] = min(low[u], tin[v]);
        }
    }

    // radacina are parintele 0 si e critica daca are cel putin doi copii dfs
    if (parinte == 0 && copii >= 2)
        critic[u] = true;
}

int main()
{
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }

    vector<int> coduri, vulnerabili;
    for (int i = 1; i <= n; i++)
    {
        if (tin[i] == 0)
        {
            coduri.push_back(i);
            dfs(i, 0);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (critic[i])
            vulnerabili.push_back(i);
    }

    fout << coduri.size() << '\n';
    for (int cod : coduri)
        fout << cod << ' ';

    fout << '\n' << vulnerabili.size() << '\n';
    for (int copil : vulnerabili)
        fout << copil << ' ';

    fout << '\n';
    return 0;
}