Pagini recente » Cod sursa (job #1247439) | Cod sursa (job #2188914) | Cod sursa (job #2087225) | Cod sursa (job #2516614) | Cod sursa (job #2143334)
#include <fstream>
#include <vector>
#include <unordered_set>
#include <stack>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> v[100003];
struct ele
{
int x,y;
ele(int a, int b):x(a),y(b){}
ele(){}
};
ele edge;
unordered_set<int> ms[100004];
stack <struct ele> s;
int niv[100004],nic[100004],nr=0,start;
bool viz[100004];
void DFS(int i)
{
for(const int&j:v[i])
{
if(viz[j]==0)
{
s.push(ele(i,j));
viz[j] = 1;
niv[j]= niv[i]+1; nic[j]=niv[j];
DFS(j);
nic[i]= min(nic[j],nic[i]);
if (nic[j] >= niv[i])
{
do
{
edge = s.top();
s.pop();
ms[nr].insert(edge.x);
ms[nr].insert(edge.y);
}
while(!((edge.x==i &&edge.y==j) ||(edge.x==j &&edge.y==i)));
nr++;
}
}
else if (niv[j]<nic[i] && niv[j]!=niv[i]-1)
nic[i] = niv[j];
}
}
int main()
{
int n,m,i,x,y;
in>>n>>m;
for(i=0;i<m;i++)
{
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
start = 1;
niv[start]= nic[start]= viz[start]=1;
DFS(start);//incepem dfs
out<<nr<<"\n";
for(i=0;i<nr;i++)
{
for(const int&e : ms[i])
out<<e<<" ";
out<<"\n";
}
return 0;
}