Cod sursa(job #3269039)

Utilizator abelesefBurduhos Abel abelesef Data 18 ianuarie 2025 10:30:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> adj[100005],adj1[100005],ans;
int viz[100005];
int in[100005];
int n,m,x,y;
queue<int> q;
vector<int> final;
stack<int> st;

void dfs(int el) {
        viz[el] = 1;
        for (auto nod : adj[el]) {
                if (viz[nod]==0)
                        dfs(nod);
        }
        st.push(el);
}

void dfs1(int nod) {
        viz[nod] = 1;
        final.push_back(nod);
        for (auto el : adj1[nod]) {
                if (viz[el]==0) {
                        dfs1(el);
                }
        }
}

int main() {
        fin>>n>>m;
        for (int i = 1;i<=m;++i) {
                fin>>x>>y;
                adj[x].push_back(y);
                adj1[y].push_back(x);
        }

        for (int i = 1;i<=n;++i) {
                if (viz[i]==0) {
                        dfs(i);
                }
        }
        for (int i = 1;i<=n;++i)
                viz[i] = 0;
        int comp = 0;
        while (!st.empty()) {
                auto el = st.top();
                st.pop();
                if (viz[el]==0) {
                        comp++;
                        dfs1(el);
                        final.push_back(-1);
                }
        }
        fout<<comp<<'\n';
        for (auto el : final) {
                if (el==-1) {
                        fout<<'\n';
                        continue;
                }
                fout<<el<<" ";
        }
        return 0;
}