Pagini recente » Cod sursa (job #2016481) | Cod sursa (job #3326767) | Cod sursa (job #3338211) | Cod sursa (job #3312685) | Cod sursa (job #3339103)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct types{
int x;int y;int id;
};
int n,m;
int global = 1;
stack <types> st;
vector<set<int>> comp;
vector<vector<pair<int,int>>> v;
vector<int> t;
vector<bool> checked;
vector<int> low;
void addcomp(int nod,int newnod,int id){
set<int> temp;
while(st.size()){
int x = st.top().x;
int y = st.top().y;
int newid = st.top().id;
temp.insert(x);
temp.insert(y);
st.pop();
if(newid == id)
break;
}
if(temp.size())
comp.push_back(temp);
}
void dfs(int nod,int mid){
checked[nod] = 1;
t[nod] = global;
low[nod] = t[nod];
global++;
for(int i = 0 ;i < v[nod].size();i++){
int newnod = v[nod][i].first;
int id = v[nod][i].second;
if(checked[newnod] == 0){
st.push({nod,newnod,id});
dfs(newnod,id);
low[nod] = min(low[nod],low[newnod]);
if(low[newnod] >= t[nod])
addcomp(nod,newnod,id);
}else if(id != mid and t[nod] > t[newnod]){
st.push({nod,newnod,id});
low[nod] = min(low[nod],t[newnod]);
}
}
}
int main(){
fin>>n>>m;
v.resize(n+1);
t.resize(n+1);
low.resize(n+1);
checked.resize(n+1,0);
for(int i=1;i<=m;i++){
int x,y;
fin>>x>>y;
v[x].push_back({y,i});
v[y].push_back({x,i});
}
for(int i=1;i<=n;i++){
if(!checked[i])
dfs(i,0);
}
fout<<comp.size()<<"\n";
for(int i = 0;i<comp.size();i++){
for(auto j:comp[i]){
fout<<j<<" ";
}
fout<<"\n";
}
}