Pagini recente » Cod sursa (job #1981462) | Cod sursa (job #164638) | Cod sursa (job #739998) | Cod sursa (job #1449210) | Cod sursa (job #1787386)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMax = 100005;
int N,M,K;
bool Use[NMax],Critical[NMax];
int Level[NMax],Low[NMax];
stack <int> S1,S2;
vector <int> G[NMax],CB[2*NMax];
void Read()
{
fin>>N>>M;
for(int i = 1; i <= M; i++)
{
int x,y;
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Sol(int x,int y)
{
int nod1,nod2;
nod1 = nod2 = 0;
while(nod1 != x && nod2 != y)
{
nod1 = S1.top();
nod2 = S2.top();
CB[K].push_back(nod1);
CB[K].push_back(nod2);
S1.pop();
S2.pop();
}
}
void DFS(int Nod, int Father)
{
Use[Nod] = 1;
Level[Nod] = Level[Father] + 1;
Low[Nod] = Level[Nod];
for(int i = 0 ; i < (int)G[Nod].size(); ++i)
{
int Vecin = G[Nod][i];
if(Vecin == Father)
continue;
if(!Use[Vecin])
{
S1.push(Nod);
S2.push(Vecin);
DFS(Vecin,Nod);
Low[Nod] = min(Low[Nod],Low[Vecin]);
if(Low[Vecin] >= Level[Nod])
{ K++; Sol(Nod,Vecin); }
}
else
Low[Nod] = min(Low[Nod],Level[Vecin]);
}
}
void Print()
{
fout<<K<<"\n";
for(int i = 1 ; i <= K ; ++i)
{
sort(CB[i].begin(),CB[i].end());
CB[i].erase( unique( CB[i].begin() , CB[i].end() ) , CB[i].end() );
for(int j = 0 ; j < (int) CB[i].size() ; ++j)
fout<<CB[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
Read();
DFS(1,0);
Print();
return 0;
}