Pagini recente » Cod sursa (job #61393) | Cod sursa (job #1619699) | Cod sursa (job #93671) | Cod sursa (job #2395825) | Cod sursa (job #2253957)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define MAX 100005
vector<int> adj[MAX], lvl, low;
vector < vector<int> > sol;
stack < pair<int,int> > st;
void createComponent(int a, int b){
vector<int> comp;
int x,y;
do{
x=st.top().first; y=st.top().second;
st.pop();
comp.push_back(x); comp.push_back(y);
}while(x!=a || y!=b);
sol.push_back(comp);
}
void dfs(int n,int from, int level){
low[n]=lvl[n]=level;
vector<int> :: iterator it;
for(it=adj[n].begin(); it!=adj[n].end();it++){
if(*it==from) continue;
if(lvl[*it]==-1){
st.push(make_pair(n,*it));
dfs(*it,n,level+1);
low[n]=min(low[n],low[*it]);
if(low[*it]>=lvl[n]) //nu ajung mai sus prin fii printr-o muchie de intoarcere
createComponent(n,*it);
}
else // => muchie intoarcere
low[n]=min(low[n],lvl[*it]);
}
}
int main(){
ifstream in("biconex.in"); ofstream out("biconex.out");
int i,n,m,x,y;
//cirire
in>>n>>m;
lvl.resize(n+1); low.resize(n+1);
lvl.assign(n+1,-1);
for(i=0;i<m;i++){
in>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
//parc adancime + rezolvare
dfs(1,0,0);
//afisare sol
out<<sol.size()<<'\n';
for(i=0;i<sol.size();i++){
sort(sol[i].begin(),sol[i].end());
sol[i].resize( distance( sol[i].begin(),unique( sol[i].begin(),sol[i].end() ) ) );
for(int j=0;j<sol[i].size();j++)
out<<sol[i][j]<<" ";
out<<'\n';
}
in.close(); out.close();
return 0;
}