Pagini recente » Cod sursa (job #1448046) | Cod sursa (job #2847528) | Cod sursa (job #2297752) | Cod sursa (job #1058352) | Cod sursa (job #2674261)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> lista[100005];
int n, m;
int daddy[100005];
int low[100005];
int dfn[100005];
int viz[100005];
struct ura{
int x, y;
};
ura st[200005];
vector <int> comp[100005];
int cnt, k = 0, cntc;
void dfs(int nod, int ord)
{
low[nod] = ord; ///low[u] = min(dfn[w]) unde w stramos al lui u si exista edge de la un fiu de al lui u la w
dfn[nod] = ord; ///ordinea in dfs
int sons = 0, i, ok = 0;
for (i = 0; i < lista[nod].size(); i++)
{
int x = lista[nod][i];
if (viz[x])
{
if (daddy[nod] == x)
{
low[nod] = min(low[nod], dfn[x]);
continue;
}
if (low[nod] > dfn[x])
{
low[nod] = dfn[x];
st[++k] = {nod, x};
}
continue;
}
sons++;
viz[x] = 1;
daddy[x] = nod;
cnt++;
st[++k] = {nod, x};
dfs(x, cnt);
low[nod] = min(low[nod], low[x]);
if (daddy[nod] == -1 && sons > 1)
{
cntc++;
while (st[k].x != nod || st[k].y != x)
{
comp[cntc].push_back(st[k].y);
k--;
}
comp[cntc].push_back(x);
if (comp[cntc][0] != nod)
comp[cntc].push_back(nod);
k--;
}
else
if (low[x] >= dfn[nod] && daddy[nod] > 0)
{
ok = 1;
cntc++;
while (k && (st[k].x != nod || st[k].y != x))
{
comp[cntc].push_back(st[k].y);
k--;
}
comp[cntc].push_back(x);
if (comp[cntc][0] != nod)
comp[cntc].push_back(nod);
k--;
}
}
}
int main()
{
int i;
cin >> n >> m;
for (i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
lista[x].push_back(y);
lista[y].push_back(x);
}
viz[1] = 1;
cnt = 1;
cntc = 0;
daddy[1] = -1;
dfs(1, 1);
if (k)
{
cntc++;
while (k > 1)
{
comp[cntc].push_back(st[k].y);
k--;
}
comp[cntc].push_back(st[k].y);
if (comp[cntc][0] != st[k].x)
comp[cntc].push_back(st[k].x);
}
cout << cntc;
for (i = 1; i <= cntc; i++)
{
cout << '\n';
for (int j = 0; j < comp[i].size(); j++)
cout << comp[i][j] << " ";
}
return 0;
}