Pagini recente » Cod sursa (job #537515) | Cod sursa (job #1682295) | Cod sursa (job #558713) | Cod sursa (job #1714307) | Cod sursa (job #2199800)
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100005
using namespace std;
vector<int> g[MAXN];
vector<int> component[MAXN];
stack<pair<int,int> > Stack;
int depth[MAXN],low[MAXN],seen[MAXN];
int components;
void CreateComponent(int node1,int node2){
components++;
while(Stack.top().first!=node1&&Stack.top().second!=node2){
component[components].push_back(Stack.top().second);
Stack.pop();
}
component[components].push_back(node2);
component[components].push_back(node1);
Stack.pop();
}
void DFS(int node,int father){
depth[node]=low[node]=depth[father]+1;
seen[node]=1;
for(int i=0;i<g[node].size();i++){
if(!seen[g[node][i]]){
Stack.push(make_pair(node,g[node][i]));
DFS(g[node][i],node);
if(low[g[node][i]]>=depth[node])
CreateComponent(node,g[node][i]);
}
if(g[node][i]!=father)
low[node]=min(low[node],low[g[node][i]]);
}
}
int main(){
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,a,b;
fin>>n>>m;
for(int i=1;i<=m;i++){
fin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1,0);
fout<<components<<endl;
for(int i=1;i<=components;i++){
for(int j=component[i].size()-1;j>=0;j--)
fout<<component[i][j]<<' ';
fout<<endl;
}
return 0;
}