Cod sursa(job #3261804)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 7 decembrie 2024 12:32:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <deque>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <bitset>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

typedef  pair<int, int> pi;

void DFS(int nod, vector<vector<int>>& edges, vector<int>& vis, vector<int>& timeOut, int& timeElaps) {
    timeElaps += 1;
    vis[nod] = 1;

    for (int x : edges[nod]) {
        if (!vis[x]) {
            DFS(x, edges, vis, timeOut, timeElaps);
        }
    }

    timeElaps += 1;
    vis[nod] = 2;
    timeOut[nod] = timeElaps;
}

void DFST(int nod, vector<vector<int>>& edges, vector<int>& vis, vector<int>& comp) {
    comp.push_back(nod);
    vis[nod] = 1;

    for (int x : edges[nod]) {
        if (!vis[x]) {
            DFST(x, edges, vis, comp);
        }
    }

    vis[nod] = 2;
}

int getMaxVisitableWebpages() {
    int N, M;
    f >> N >> M;

    vector<vector<int>> V(N);
    vector<vector<int>> VT(N);
    for (int i = 0; i < M; i++) {
        int a, b;
      
        f >> a >> b;
        a--;
        b--;
        V[a].push_back(b);
        VT[b].push_back(a);
    }

    int timeElaps = 0;
    vector<int> vis(N, 0), timeOut(N, 0);
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            DFS(i, V, vis, timeOut, timeElaps);
        }
    }

    vector<pi> topOrder;
    for (int i = 0; i < N; i++) {
        topOrder.push_back({ i, timeOut[i] });
        //cout << i << ' ' << timeOut[i] << '\n';
        vis[i] = 0;
    }
    sort(topOrder.begin(), topOrder.end(), [&](const pi& X, const pi& Y) {
      return X.second <= Y.second;
        });

    topOrder.resize(topOrder.size());

    vector<vector<int>> ans;
    for (int i = N - 1; i >= 0; i--) {
        if (!vis[topOrder[i].first]) {
            vector<int> comp;
            DFST(topOrder[i].first, VT, vis, comp);
            ans.push_back(comp);
        }
    }

    g << ans.size() << '\n';
    for (vector<int>& comp : ans) {
        for (int el : comp) {
            g << el + 1 << ' ';
        }
        g << '\n';
    }

    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    getMaxVisitableWebpages();
    return 0;
}