Pagini recente » Cod sursa (job #1492248) | Cod sursa (job #2765174) | Cod sursa (job #708667) | Cod sursa (job #2265517) | Cod sursa (job #2206257)
#include<bits/stdc++.h>
using namespace std;
vector<list<int> > G, Sol;
vector<int> Prev, Disc, Low;
stack<pair<int,int> > S;
vector<bool> ArticVertex;
void FindArticVertex(int node, int &time,int &nr)
{
time++;
Disc[node] = Low[node] = time;
for(int u : G[node])
{
if(!Disc[u])
{
S.push(make_pair(node,u));
Prev[u] = node;
FindArticVertex(u, time, nr);
if(Low[u] >= Disc[node])
{
int a,b;
nr++;
do{
a = S.top().first;
b = S.top().second;
S.pop();
Sol[nr].push_back(b);
}while(a!= node && b!= u);
Sol[nr].push_back(node);
}
Low[node] = min(Low[node],Low[u]);
}
else
if(u != Prev[node])
Low[node] = min(Low[node], Low[u]);
}
}
int main()
{
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m, x, y, time = 0, nr = 0;
in>>n>>m;
G.resize(n+1);
Sol.resize(n+1);
Prev.resize(n+1, -1);
Disc.resize(n+1);
ArticVertex.resize(n+1);
Low.resize(n+1);
for(int i=1; i<=m; i++)
{
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!Disc[i])
FindArticVertex(i, time, nr);
out<<nr<<'\n';
for(int i=1; i<=nr; i++)
{
for(int u : Sol[i])
out<<u<<" ";
out<<'\n';
}
return 0;
}