Pagini recente » Cod sursa (job #2895955) | Cod sursa (job #1028753) | Cod sursa (job #879595) | Cod sursa (job #2575743) | Cod sursa (job #2924630)
#include <fstream>
#include<vector>
#include<stack>
#include<cstring>
#include<unordered_set>
using namespace std;
#define MAXN 100005
#define NIL -1
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> g[MAXN];
vector<vector<int> >bic;
int df[MAXN], edge[MAXN];
stack<pair<int, int> > s;
void constructBick(int a, int b){
pair<int, int> goldStandard=make_pair(a, b), p;///standardul de aur
pair<int, int> silver={b, a};
vector<int> currComp;
do{
p=s.top();///golim stiva, facem biconexa de pana acum
currComp.push_back(p.first);
currComp.push_back(p.second);
s.pop();
}while(p!=goldStandard&&s.size()>0);
bic.push_back(currComp);
}
void dfs(int i, int prev, int depth){///stiva dfs e inerenta in recursie
df[i]=edge[i]=depth;
for(int j=0; j<g[i].size(); j++){
if(g[i][j]!=prev){ ///daca nu se intoarce
if(df[g[i][j]]==NIL){//daca e nevizitat
s.push(make_pair(i, g[i][j]));//muchia merge pe stiva
dfs(g[i][j], i, depth+1);
edge[i]=min(edge[i], edge[g[i][j]]);
if(edge[g[i][j]]>=df[i])
constructBick(i, g[i][j]);
}
else{///am muchie inapoi in arborele DFS
edge[i]=min(edge[i], df[g[i][j]]);//o pun
}
}
}
}
void filterVector(vector<int> a){
unordered_set<int> s; int n=a.size();
for(int i=0; i<n; i++){
if(s.find(a[i])==s.end()){
fout<<a[i]<<" ";
}
s.insert(a[i]);
}
fout<<"\n";
}
int main()
{
int n, e; fin>>n>>e;
for(int i=0; i<e; i++){
int x, y; fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
memset(df, NIL, sizeof(df));///cifram diferit nevizitarea de adancimea nula
dfs(1, 0, 0);
fout<<bic.size()<<"\n";
for(int i=0; i<bic.size(); i++){
filterVector(bic[i]);
}
return 0;
}