Pagini recente » Cod sursa (job #818380) | Cod sursa (job #495458) | Cod sursa (job #555103) | Cod sursa (job #264905) | Cod sursa (job #2798230)
#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]]==0){
visited[adjList[x][i]]++;
DFS(adjList[x][i],x);
low[x]=min(low[x],low[adjList[x][i]]);
if(id[x]<=low[adjList[x][i]]){
while(!st.empty() && st.top()!=adjList[x][i]){
aux.push_back(st.top()+1);
st.pop();
}
aux.push_back(adjList[x][i]+1);
st.pop();
aux.push_back(x+1);
res.push_back(aux);
aux.clear();
}
}
else{
low[x]=min(low[x],id[adjList[x][i]]);
}
}
}
}
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-1].push_back(b-1);
adjList[b-1].push_back(a-1);
}
for(i=0;i<n;++i){
if(visited[i]==0){
visited[i]++;
DFS(i,-1);
while(!st.empty()){
st.pop();
}
}
}
int j;
g<<res.size()<<'\n';
for(i=0;i<res.size();++i){
for(j=0;j<res[i].size();++j){
g<<res[i][j]<<' ';
}
g<<'\n';
}
return 0;
}