Pagini recente » Cod sursa (job #2081511) | Cod sursa (job #2451536) | Cod sursa (job #3275486) | Cod sursa (job #2432108) | Cod sursa (job #1404238)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100005
using namespace std;
FILE *fi, *fo;
int n, m, nrComp;
int tata[nmax], low[nmax], nivel[nmax];
stack < pair<int, int> > s;
vector <int> G[nmax], sol[nmax];
bool viz[nmax];
void newComp(int x, int y)
{
int X = s.top().first;
int Y = s.top().second;
s.pop();
while (X != x && Y != y)
{
sol[nrComp].push_back(X);
sol[nrComp].push_back(Y);
X = s.top().first;
Y = s.top().second;
s.pop();
}
sol[nrComp].push_back(X);
sol[nrComp].push_back(Y);
}
void dfs(int nod)
{
viz[nod] = true;
for (int i = 0; i < G[nod].size(); i++)
{
int vecin = G[nod][i];
if (!viz[vecin])
{
low[vecin] = nivel[vecin] = nivel[nod] + 1;
tata[vecin] = nod;
s.push(make_pair(nod, vecin));
dfs(vecin);
low[nod] = min(low[nod], low[vecin]);
if (low[vecin] >= nivel[nod])
{
nrComp++;
newComp(nod, vecin);
}
}
else if (tata[nod] != vecin)
low[nod] = min(low[nod], nivel[vecin]);
}
}
int main()
{
ifstream fi("biconex.in");
ofstream fo("biconex.out");
fi >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fi >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
fo << nrComp << "\n";
for (int i = 1; i <= nrComp; i++)
{
sort(sol[i].begin(), sol[i].end());
fo << sol[i][0] << " ";
for (int j = 1; j < sol[i].size(); j++)
if (sol[i][j] != sol[i][j-1])
fo << sol[i][j] << " ";
fo << "\n";
}
fi.close();
fo.close();
return 0;
}