Pagini recente » Cod sursa (job #1528311) | Cod sursa (job #1439772) | Cod sursa (job #1061066) | Cod sursa (job #2642218) | Cod sursa (job #2616264)
#include<bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int num_nodes,num_edges;
vector<int> graph[100000];
vector<int> dfs_graph[100000];
vector<vector<int>> biconnected;
bool visited[100000];
int parent[100000];
int depth[100000];
int lowest_depth[100000];
int current_time=0;
void createDfsTree(int node){
depth[node]=current_time;
lowest_depth[node]=current_time;
current_time++;
visited[node]=true;
for(int child:graph[node]){
if(!visited[child]){
dfs_graph[node].push_back(child);
parent[child]=node;
createDfsTree(child);
lowest_depth[node]=min(lowest_depth[node],lowest_depth[child]);
}
else if(child!=parent[node]){
lowest_depth[node]=min(lowest_depth[node],depth[child]);
}
}
}
void addSubgraph(int node,vector<int>&to_add){
to_add.push_back(node);
for(int a:dfs_graph[node])
addSubgraph(a,to_add);
}
void findBiconnected(int node){
bool root=false;
if(parent[node]==-1)
root=true;
for(int i=0;i<dfs_graph[node].size();i++){
int child=dfs_graph[node][i];
findBiconnected(child);
if((!root && lowest_depth[child]>=depth[node]) || (root && dfs_graph[node].size()>=2)){
vector<int> comp;
dfs_graph[node].erase(dfs_graph[node].begin()+i);
i--;
comp.push_back(node);
addSubgraph(child,comp);
biconnected.push_back(comp);
}
}
}
void read(){
in>>num_nodes>>num_edges;
int a,b;
for(int i=0;i<num_edges;i++){
in>>a>>b;
graph[a-1].push_back(b-1);
graph[b-1].push_back(a-1);
}
for(int i=0;i<num_nodes;i++)
parent[i]=-1;
}
void solve(){
createDfsTree(0);
findBiconnected(0);
vector<int> remaining;
addSubgraph(0,remaining);
biconnected.push_back(remaining);
out<<biconnected.size()<<endl;
for(int i=0;i<biconnected.size();i++){
for(int a:biconnected[i])
out<<a+1<<" ";
out<<endl;
}
}
int main(){
read();
solve();
return 0;
}