Pagini recente » Cod sursa (job #3242741) | Cod sursa (job #1752305) | Cod sursa (job #1702599) | Cod sursa (job #1392607) | Cod sursa (job #1669520)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<bitset>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int const NMax = 100005;
int lv[NMax], low[NMax];
bitset <NMax> use;
vector <int> G[NMax], CBC[NMax];
stack <pair <int, int> > S;
int n, m, cbc;
void Read()
{
int i, x, y;
f>>n>>m;
for(i=1; i<=m; i++){
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void DFS(int nod, int tata)
{
vector <int>::iterator it;
use[nod] = 1;
lv[nod] = lv[tata] + 1;
low[nod] = lv[nod];
for(it = G[nod].begin(); it != G[nod].end(); it++){
if(use[*it])
low[nod] = min(low[nod], lv[*it]);
if(!use[*it]){
S.push(make_pair(nod, *it));
DFS(*it, nod);
low[nod] = min(low[nod], low[*it]);
if(low[*it] >= lv[nod]){
cbc++;
while(S.top().first != nod && S.top().second != (*it)){
CBC[cbc].push_back(S.top().second);
S.pop();
}
CBC[cbc].push_back(*it);
CBC[cbc].push_back(nod);
S.pop();
}
}
}
}
void Print()
{
int i;
vector <int>::iterator it;
g<<cbc<<"\n";
for(i=1; i<=cbc; i++){
for(it = CBC[i].begin(); it != CBC[i].end(); it++)
g<<(*it)<<" ";
g<<"\n";
}
}
int main()
{
Read();
DFS(1, 0);
Print();
return 0;
}