Pagini recente » Cod sursa (job #1520622) | Cod sursa (job #896958) | Cod sursa (job #3293597) | Cod sursa (job #796392) | Cod sursa (job #2798214)
#include<bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> visited,adjList[100001],low,id;
int temp=0,cnt=0;
stack<int> st;
vector<vector<int>> res;
vector<int> aux;
void DFS(int x, int parent){
int i;
id[x]=temp;
low[x]=temp;
temp++;
st.push(x);
for(i=0;i<adjList[x].size();++i){
if(parent!=adjList[x][i]){
if(visited[adjList[x][i]-1]==0){
visited[adjList[x][i]-1]++;
DFS(adjList[x][i],x);
low[x-1]=min(low[x-1],low[adjList[x][i]-1]);
if(id[x-1]<=low[adjList[x][i]-1]){
cnt++;
while(!st.empty() && st.top()!=adjList[x][i]){
aux.push_back(st.top());
st.pop();
}
aux.push_back(adjList[x][i]);
st.pop();
aux.push_back(x);
res.push_back(aux);
aux.clear();
}
}
else{
low[x-1]=min(low[x-1],id[adjList[x][i]-1]);
}
}
}
}
int main(){
int i;
int n,m,a,b;
f>>n>>m;
for(i=0;i<n;++i){
visited.push_back(0);
id.push_back(0);
low.push_back(0);
}
for(i=0;i<m;++i){
f>>a>>b;
adjList[a].push_back(b);
adjList[b].push_back(a);
}
visited[0]++;
DFS(1,-1);
unordered_map<int,vector<int>>umap;
for(i=0;i<low.size();++i){
umap[low[i]].push_back(i+1);
}
int j;
g<<cnt<<'\n';
for(i=0;i<res.size();++i){
for(j=0;j<res[i].size();++j){
g<<res[i][j]<<' ';
}
g<<'\n';
}
return 0;
}