Cod sursa(job #3374690)

Utilizator AlexPopescuPopescu Alexandru AlexPopescu Data 9 noiembrie 2026 09:23:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.94 kb
#include <bits/stdc++.h>
using namespace std;


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

vector<vector<int>>graph;
vector<int>discovery,low,parent,index_of_next_neighbour;
vector<bool>visited;
vector<vector<int>>components;
vector<pair<int,int>>edge_stack;
int timer_;

void close_component(int x,int y)
   { vector<int>team;
     set<int>nodes_in_component;
     while(!edge_stack.empty())
          { pair<int,int>current_edge=edge_stack.back();
            edge_stack.pop_back();
            nodes_in_component.insert(current_edge.first);
            nodes_in_component.insert(current_edge.second);
            if(current_edge.first==x&&current_edge.second==y)
                break;
          }
     for(auto &node:nodes_in_component)
         team.push_back(node);
     components.push_back(team);
   }

void dfs(int start)
   { stack<int>node_list;
     node_list.push(start);
     visited[start]=true;
     parent[start]=0;
     discovery[start]=low[start]=++timer_;
     while(!node_list.empty())
          { int current_node=node_list.top();
            int index_of_next=index_of_next_neighbour[current_node];
            if(index_of_next==(int)graph[current_node].size())
               { node_list.pop();
                 if(parent[current_node]!=0)
                    { int p=parent[current_node];
                      low[p]=min(low[p],low[current_node]);
                      if(low[current_node]>=discovery[p])
                          close_component(p,current_node);
                    }
                 continue;
               }
            index_of_next_neighbour[current_node]++;
            int neighbour=graph[current_node][index_of_next];
            if(neighbour==parent[current_node])
                continue;
            if(visited[neighbour])
               { if(discovery[neighbour]<discovery[current_node])
                     edge_stack.push_back({current_node,neighbour});
                 low[current_node]=min(low[current_node],discovery[neighbour]);
               }
            else
               { edge_stack.push_back({current_node,neighbour});
                 parent[neighbour]=current_node;
                 visited[neighbour]=true;
                 discovery[neighbour]=low[neighbour]=++timer_;
                 node_list.push(neighbour);
               }
          }
   }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M;
    fin>>N>>M;
    graph.resize(N+1);
    discovery.assign(N+1,0);
    low.assign(N+1,0);
    parent.assign(N+1,0);
    index_of_next_neighbour.assign(N+1,0);
    visited.assign(N+1,false);
    for(int i=1;i<=M;i++)
        { int x,y;
          fin>>x>>y;
          graph[x].push_back(y);
          graph[y].push_back(x);
        }
    for(int i=1;i<=N;i++)
        if(!visited[i])
            dfs(i);
    fout<<components.size()<<'\n';
    for(auto &team:components)
         { for(auto &node:team)
               fout<<node<<' ';
           fout<<'\n';
         }
    return 0;
}