Pagini recente » Monitorul de evaluare | Cod sursa (job #1152506) | Cod sursa (job #695877) | Cod sursa (job #685862) | Cod sursa (job #701091)
Cod sursa(job #701091)
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100005
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> V[nmax];
vector<int> Sol[nmax];
stack<pair<int,int> > S;
int Intoarcere[nmax],T[nmax],Nivel[nmax],Atinge;
int N,M,nr;
inline int _min(int a,int b){if(a<b)return a;return b;}
void Add(int x,int nod)
{
int a,b;
do
{
a=S.top().first,b=S.top().second;
S.pop();
Sol[nr].push_back(a);
}
while(a!=x||b!=nod);
Sol[nr].push_back(nod);
nr++;
}
void DFS(int nod)
{
int i,x;
Intoarcere[nod] = Nivel[nod];
for(i=0;i<V[nod].size();i++)
{
x = V[nod][i];
if(!Nivel[x])//nu a fost parcurs
{
T[x] = nod;
S.push(make_pair(x,nod));
Nivel[x] = Nivel[nod]+1;
if(nod==1)Atinge++;
DFS(x);
Intoarcere[nod]=_min(Intoarcere[nod],Intoarcere[x]);
if(Intoarcere[x]>=Nivel[nod])//nu pot ajunge mai sus deci nod e critic
Add(x,nod);
}
else if(x!=T[nod])
Intoarcere[nod]=_min(Intoarcere[nod],Nivel[x]);
}
}
int main()
{
int x,y;
in>>N>>M;
while(M--)
{
in>>x>>y;
V[x].push_back(y);
V[y].push_back(x);
}
Nivel[0] = 0;
Nivel[1] = 1;
DFS(1); out<<nr<<'\n';
for(y=0;y<nr;y++)
{
for(x=0;x<Sol[y].size();x++)
out<<Sol[y][x]<<' ';
out<<'\n';
}
return 0;
}