Cod sursa(job #3285758)

Utilizator Dulea_AndreiDulea Andrei-Lucian Dulea_Andrei Data 13 martie 2025 14:12:39
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <bits/stdc++.h>
using namespace std;

void DFS1(const vector<vector<int>> &adj, vector<bool> &visited, int s, stack<int> &finishStack)
{
    visited[s] = true;
    for (int v : adj[s])
        if (!visited[v])
            DFS1(adj, visited, v, finishStack);

    finishStack.push(s);
}

void DFS2(const vector<vector<int>> &adj, vector<bool> &visited, int s, vector<int>&currentComponent)
{
    visited[s] = true;
    currentComponent.push_back(s);
    for (int v : adj[s])
        if (!visited[v])
            DFS2(adj, visited, v,currentComponent);
}

int kosarajuSCC(const vector<vector<int>> &graph, const vector<vector<int>> &revGraph, int n, vector<vector<int>>&newGraph)
{
    stack<int> finishStack;
    vector<bool> visited(n + 1, false);

    // primul DFS pe graful original pentru a determina ordinea de terminare.
    for(int i = 1; i <= n; i++)
        if (!visited[i])
            DFS1(graph, visited, i, finishStack);

    // al doilea DFS pe graful inversat
    int sccCount = 0;
    fill(visited.begin(), visited.end(), false);
    while(!finishStack.empty())
    {
        int node = finishStack.top();
        finishStack.pop();
        if (!visited[node])
        {
            vector<int>currentComponent;
            DFS2(revGraph, visited, node,currentComponent);
            newGraph.push_back(currentComponent);
            sccCount++;

        }
    }
    return sccCount;
}

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n, m, x, y;
    fin >> n >> m;

    vector<vector<int>> graph(n + 1), revGraph(n + 1);
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y;
        graph[x].push_back(y);
        revGraph[y].push_back(x);
    }

    for (int i = 1; i <= n; i++)
    {
        sort(graph[i].begin(), graph[i].end());
        sort(revGraph[i].begin(), revGraph[i].end());
    }
    vector<vector<int>>newGraph;

    int sccCount = kosarajuSCC(graph, revGraph, n, newGraph);
    cout << sccCount << "\n";
    for(int i = 0; i < sccCount; i++)
    {
        for(auto j:newGraph[i])
        {
            fout <<j<<" ";
        }
        fout <<"\n";
    }
    return 0;
}