Cod sursa(job #2981078)

Utilizator Elvis_CostinTuca Elvis-Costin Elvis_Costin Data 17 februarie 2023 10:43:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;
string np = "ctc";
ifstream f(np + ".in");
ofstream g(np + ".out");

// #define f cin
// #define g cout

int n, m, val, valori[100003];
bool viz[100003];
vector<int> adj1[100003], adj2[100003];
stack<int> st;

void dfs1(int nod)
{
    viz[nod] = 1;
    for (auto u : adj1[nod])
        if (!viz[u])
            dfs1(u);
    st.push(nod);
}
void dfs2(int nod)
{
    viz[nod] = 0;
    valori[nod] = val;
    for (auto u : adj2[nod])
        if (viz[u])
            dfs2(u);
}
int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);

    f >> n >> m;
    for (int a, b; f >> a >> b;)
        adj1[a].emplace_back(b), adj2[b].emplace_back(a);

    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs1(i);

    while (!st.empty())
    {
        int curr = st.top();
        st.pop();
        if (viz[curr])
            val++, dfs2(curr);
    }

    vector<int> rez[val + 1];
    for (int i = 1; i <= n; i++)
        rez[valori[i]].push_back(i);

    g << val << '\n';
    for (int i = 1; i <= val; i++, g << '\n')
        for (auto x : rez[i])
            g << x << " ";

    return 0;
}