Pagini recente » Cod sursa (job #2534457) | Cod sursa (job #2642949) | Cod sursa (job #2533823) | Cod sursa (job #1131575) | Cod sursa (job #2557128)
#include <iostream>
#include <cstdio>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int N = 100000;
struct nod{
int num, low, parent;
} nodes[N+1];
bool visited[N+1];
bool articulation[N+1];
vector <int> g[N+1];
vector <int> stiva;
vector <int> comp[N+1];
int timp, rootChildren, root;
int compNr;
void dfs(int node){
stiva.push_back(node);
visited[node] = true;
nodes[node].low = nodes[node].num = timp++;
for(int p=0; p<(int)g[node].size(); p++){
int next = g[node][p];
if(!visited[next]){
nodes[next].parent = node;
if(node == root)
rootChildren++;
dfs(next);
if(nodes[node].num <= nodes[next].low){
articulation[node] = true;
compNr++;
while(stiva.back() != next){
comp[compNr].push_back(stiva.back());
stiva.pop_back();
}
comp[compNr].push_back(next);
comp[compNr].push_back(node);
stiva.pop_back();
}
nodes[node].low = min(nodes[node].low, nodes[next].low);
}
else if(next != nodes[node].parent)
nodes[node].low = min(nodes[node].low, nodes[next].num);
}
}
int main()
{
int n,m,i,x,y;
fin >> n >> m;
for(i=0; i<m; i++){
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(i=1; i<=n; i++)
if(!visited[i]){
timp = 0, rootChildren = 0, root = i;
dfs(i);
articulation[i] = (rootChildren > 1);
}
fout << compNr << "\n";
for(i=1; i<=compNr; i++){
for(int j=0; j<(int)comp[i].size(); j++)
fout << comp[i][j] << " ";
fout << "\n";
}
return 0;
}