Pagini recente » Cod sursa (job #1359169) | Cod sursa (job #1744659) | Cod sursa (job #2964725) | Cod sursa (job #1025400) | Cod sursa (job #1089866)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> G[100005];
vector <int> Solution[200005];
int Result,N,M;
bool Use[100005],Critical[100005];
int Level[100005],MinLevel[100005];
stack <int> S1;
stack <int> S2;
void Read()
{
int i;
f>>N>>M;
for(i=1;i<=M;i++)
{
int x,y;
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(i=1;i<=N;i++)
MinLevel[i]=1000001,Level[i]=-1;
}
void Sol(int X,int Y)
{
int i;
int node1=0,node2=0;
++Result;
while(node1!=X && node2!=Y)
{
node1=S1.top();
node2=S2.top();
Solution[Result].push_back(node1);
Solution[Result].push_back(node2);
S1.pop();
S2.pop();
}
}
void DFS(int father,int node)
{
Use[node]=1;
Level[node]=MinLevel[node]=Level[father]+1;
for(unsigned int i=0;i<G[node].size();i++)
{
int neighbour=G[node][i];
if(neighbour==father)
continue;
if(Use[neighbour]==0)
{
S1.push(node);
S2.push(neighbour);
DFS(node,neighbour);
MinLevel[node]=min(MinLevel[node],MinLevel[neighbour]);
if(Level[node]<=MinLevel[neighbour])
Sol(node,neighbour);
}
else
MinLevel[node]=min(MinLevel[node],Level[neighbour]);
}
}
void Print()
{
int i;
g<<Result<<"\n";
for(i=1;i<=Result;i++)
{
unsigned int j=0;
sort(Solution[i].begin(), Solution[i].end());
Solution[i].erase(unique(Solution[i].begin(), Solution[i].end()), Solution[i].end());
for(j=0;j<Solution[i].size();j++)
g<<Solution[i][j]<<" ";
g<<"\n";
}
}
int main()
{
Read();
DFS(0,1);
Print();
return 0;
}