Pagini recente » Cod sursa (job #699228) | Cod sursa (job #1816318) | Cod sursa (job #3038168) | Cod sursa (job #729274) | Cod sursa (job #1414341)
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> V[100002];
int niv[100002], minniv[100002];
int ST[100002];
bool S[100002];
vector<vector<int> > comp;
void Dfs(int x)
{
S[x] = true;
minniv[x] = niv[x];
ST[++ST[0]] = x;
for (auto nod : V[x])
if (!S[nod])
{
niv[nod] = niv[x] + 1;
Dfs(nod);
minniv[x] = min(minniv[x], minniv[nod]);
if (minniv[nod] >= niv[x])
{
comp.push_back(vector<int>());
while (true)
{
comp.back().push_back(ST[ST[0]]);
--ST[0];
if (ST[ST[0] + 1] == nod) break;
}
comp.back().push_back(x);
}
}
else if (niv[nod] < niv[x])
minniv[x] = min(minniv[x], niv[nod]);
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
fin >> N >> M;
for (int i = 1, nod1, nod2; i <= M; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
V[nod2].push_back(nod1);
}
for (int i = 1; i <= N; ++i)
if (!S[i])
Dfs(i);
fout << comp.size() << '\n';
for (auto c : comp)
{
for (auto nod : c)
fout << nod << ' ';
fout << '\n';
}
fin.close();
fout.close();
}