Cod sursa(job #3371992)

Utilizator AlexPopescuPopescu Alexandru AlexPopescu Data 2 noiembrie 2026 01:19:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
#include <bits/stdc++.h>
using namespace std;

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

void first_dfs(int node,vector<vector<int>>&graph,vector<bool>&visited,
               stack<int>&reverse_nodes,vector<int>&ptr)
{
    stack<pair<int,bool>>node_list;
    node_list.push({node,false});
    visited[node]=true;
    while(!node_list.empty())
    {
        int current_node=node_list.top().first;
        if(node_list.top().second)
        {
            reverse_nodes.push(current_node);
            node_list.pop();
            continue;
        }
        if(ptr[current_node]==(int)graph[current_node].size())
        {
            node_list.top().second=true;
            continue;
        }
        int neighbour=graph[current_node][ptr[current_node]++];
        if(!visited[neighbour])
        {
            visited[neighbour]=true;
            node_list.push({neighbour,false});
        }
    }
}

void second_dfs(int node,vector<vector<int>>&graph,vector<bool>&visited,
                vector<vector<int>>&components)
{
    stack<int>node_list;
    vector<int>nodes;
    node_list.push(node);
    nodes.push_back(node);
    visited[node]=true;
    while(!node_list.empty())
    {
        int current_node=node_list.top();
        node_list.pop();
        for(auto&neighbour:graph[current_node])
            if(!visited[neighbour])
            {
                node_list.push(neighbour);
                nodes.push_back(neighbour);
                visited[neighbour]=true;
            }
    }
    components.push_back(nodes);
}

int main()
{
    int N,M;
    fin>>N>>M;
    vector<vector<int>>graph(N+1);
    vector<vector<int>>transpose_graph(N+1);
    vector<bool>visited(N+1,0),visited_1(N+1,0);
    vector<int>ptr(N+1,0);
    vector<vector<int>>components;
    stack<int>stack_for_reversed_dfs;
    for(int i=1;i<=M;i++)
    {
        int x,y;
        fin>>x>>y;
        graph[x].push_back(y);
        transpose_graph[y].push_back(x);
    }
    for(int i=1;i<=N;i++)
        if(!visited[i])
            first_dfs(i,graph,visited,stack_for_reversed_dfs,ptr);
    int number_of_strongly_components=0;
    while(!stack_for_reversed_dfs.empty())
    {
        int i=stack_for_reversed_dfs.top();
        if(!visited_1[i])
        {
            second_dfs(i,transpose_graph,visited_1,components);
            number_of_strongly_components++;
        }
        stack_for_reversed_dfs.pop();
    }
    fout<<number_of_strongly_components<<'\n';
    for(auto&vec:components)
    {
        for(auto elem:vec)
            fout<<elem<<' ';
        fout<<'\n';
    }
    return 0;
}