Pagini recente » Cod sursa (job #1941440) | Cod sursa (job #707843) | Cod sursa (job #200117) | Cod sursa (job #893440) | Cod sursa (job #2143344)
#include <fstream>
#include <vector>
#include <unordered_set>
#include <stack>
#define min(a,b) ((a<b)?a:b)//folosesc macroul pt. cai mai rapid decat o functie
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> v[100003];//Acest vector contine listele de adiacenta ale grafului
struct ele
{
int x,y;
}edge;//Aceasta structura retine o muchie a grafului pe care o vom introduce in stiva
vector< unordered_set<int>> ms;
stack <struct ele> s;
vector<int> niv,nic;
int nr=0,start;
vector<bool> viz;
void DFS(int i)
{
int j;
for(auto it = v[i].begin();it!=v[i].end();++it)
{
j = *it;
if(viz[j]==0)
{
edge.x = i;
edge.y = j;
s.push(edge);
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])
{
unordered_set<int> mse;
do
{
edge = s.top();
s.pop();
if(mse.find(edge.x) == mse.end())
mse.insert(edge.x);
if(mse.find(edge.y) == mse.end())
mse.insert(edge.y);
}
while(!((edge.x==i &&edge.y==j) ||(edge.x==j &&edge.y==i)));
ms.push_back(mse);
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;
nic.resize(n+1);
niv.resize(n+1);
viz.resize(n+1); viz.assign(n+1,false);
for(i=0;i<m;i++)
{
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
start = 1;
niv[start]=1;
nic[start]=1;
viz[start]=1;
DFS(start);
out<<nr<<"\n";
for(i=0;i<nr;i++)
{
for(auto ite = ms[i].begin();ite!=ms[i].end();ite++)
out<<*ite<<" ";
out<<"\n";
}
return 0;
}