Pagini recente » Cod sursa (job #1634974) | Cod sursa (job #1639929) | Cod sursa (job #1530113) | Cod sursa (job #548973) | Cod sursa (job #2674284)
#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;
};
int st[200005];
vector <int> comp[200005];
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;
st[++k] = nod;
for (i = 0; i < lista[nod].size(); i++)
{
int x = lista[nod][i];
if (viz[x])
{
low[nod] = min(low[nod], dfn[x]);
continue;
}
sons++;
viz[x] = 1;
daddy[x] = nod;
cnt++;
dfs(x, cnt);
low[nod] = min(low[nod], low[x]);
if (low[x] >= dfn[nod])
{
cntc++;
while (k && st[k] != x)
{
comp[cntc].push_back(st[k]);
k--;
}
k--;
comp[cntc].push_back(x);
comp[cntc].push_back(nod);
}
}
}
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);
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;
}