Pagini recente » Cod sursa (job #1636630) | Cod sursa (job #2055935) | Cod sursa (job #1545217) | Cod sursa (job #1698072) | Cod sursa (job #1464883)
#include <fstream>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#define Nmax 100013
#define pb push_back
class cell {
public :
int node;
cell *prev;
cell(int a, cell *l) {node=a; prev=l;};
};
class UndirectedGraph {
private :
cell *adj[Nmax];
stack < pair<int,int > > St;
vector < vector <int> > V;
vector <int> Bic;
bool used[Nmax];
int father[Nmax];
int level[Nmax];
int levelMin[Nmax];
void __build_solution(int a,int b){
bool freq[Nmax];
memset(freq,0,sizeof freq);
while(St.top().first!=a){
int x = St.top().first;
int y = St.top().second;
if (!freq[x]) Bic.pb(x);
if (!freq[y]) Bic.pb(y);
++freq[x];
++freq[y];
St.pop();
}
if (!freq[a]) Bic.pb(a);
if (!freq[b]) Bic.pb(b);
St.pop();
sort(Bic.begin(),Bic.end());
V.pb(Bic);
Bic.clear();
}
public :
int cntBiconected = 0;
UndirectedGraph(int nodes,int edges) {
for (int i=1;i<=nodes;++i) {
adj[i]=NULL;
father[i]=i;
level[i]=levelMin[i]=Nmax;
}
level[1]=1;
levelMin[1]=1;
};
void add(int a,int b){
cell *node = new cell(a,adj[b]); adj[b]=node;
node = new cell(b,adj[a]); adj[a]=node;
}
void dfs(int node) {
used[node]=1;
for (cell *to = adj[node];to;to=to->prev){
//return edge
if (father[node]!=to->node) {
if (used[to->node]) {
if (level[to->node]<level[node]) St.push({node,to->node});
levelMin[node]=min(levelMin[node],level[to->node]);
}
//direct edge
if (!used[to->node]) {
father[to->node]=node;
levelMin[to->node]=level[to->node]=level[node]+1;
St.push({node,to->node});
dfs(to->node);
levelMin[node]=min(levelMin[node],levelMin[to->node]);
/*if the vertex-son is linked directly with his father, or
it belongs to one of his sons subtrees, result we have a new component*/
if (levelMin[to->node]>=level[node]){
++cntBiconected;
__build_solution(node,to->node);
}
}
}
}
}
void showSol(){
for (int i=0;i<V.size();++i){
for (int j=0;j<V[i].size();++j)
cout<<V[i][j]<<" ";
cout<<"\n";
}
}
};
int a,b,n,m;
int main(void) {
cin>>n>>m;
UndirectedGraph Graph(n,m);
for (int i=1;i<=m;++i) {
cin>>a>>b;
Graph.add(a,b);
}
Graph.dfs(1);
cout<<Graph.cntBiconected<<"\n";
Graph.showSol();
return 0;
}