Pagini recente » Cod sursa (job #2918468) | Cod sursa (job #1347042) | Cod sursa (job #880208) | Cod sursa (job #2575482) | Cod sursa (job #2215438)
#include <fstream>
#include <vector>
#define Nmax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> v[Nmax], sol[Nmax];
vector <int> ::iterator it;
int n, m, ans;
bool seen[Nmax];
int x, y, num_comp;
int st[Nmax], top;
int lv[Nmax], lmax[Nmax];
void GetComponent(int x, int dd)
{
sol[num_comp].push_back(dd);
while(st[top] != x && top >= 1)
{
sol[num_comp].push_back(st[top]);
top--;
}
if (top > 0)
{
sol[num_comp].push_back(x);
top--;
}
}
void dfs(int x, int dd)
{
seen[x]=true;
lmax[x]=lv[x]=lv[dd]+1;
for ( int i = 0, l=v[x].size(); i<l; i ++ )
{
int y=v[x][i];
if(y == dd) continue;
if(seen[y] == true)
{
lmax[x]=min(lmax[x], lv[y]);
continue;
}
st[++top]=y;
dfs(y, x);
lmax[x]=min(lmax[x], lmax[y]);
if(lv[x] <= lmax[y] )
{
num_comp++;
GetComponent(y, x);
}
}
}
int main()
{
f >> n >> m;
for ( int i = 1; i <= m; i ++ )
{
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for ( int i = 1; i <= n; i ++ )
if(seen[i] == false)
dfs(i,0);
g << num_comp << '\n';
for ( int i = 1; i <= num_comp; i ++ )
{
for ( it=sol[i].begin(); it != sol[i].end(); it ++ )
g << *it << " ";
g << '\n';
}
}