Pagini recente » Cod sursa (job #1904934) | Cod sursa (job #75140) | Cod sursa (job #2740573) | Cod sursa (job #2023711) | Cod sursa (job #1928854)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define nmax 100005
using namespace std;
int n, m, nr, nrcmp;
vector <int> dfn (nmax, -1), low(nmax, -1);
vector <int> G[nmax];
vector <int> componente[nmax];
stack <pair <int, int> > stiva;
void read()
{
ifstream f("biconex.in");
f >> n >> m;
for(int x, y; m; --m)
{
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
f.close();
}
void golire_stiva(int nod, int tata)
{
++nrcmp;
int x, y;
do
{
x = stiva.top().first; y = stiva.top().second;
stiva.pop();
componente[nrcmp].push_back(x), componente[nrcmp].push_back(y);
} while(x != nod || y != tata);
}
void dfs(int nod, int tata)
{
dfn[nod] = ++nr;
low[nod] = nr;
for(int i=0; i<G[nod].size(); ++i)
{
if(G[nod][i] == tata) continue;
if(dfn[G[nod][i]] == -1)
{
stiva.push(make_pair(G[nod][i], nod));
dfs(G[nod][i], nod);
low[nod] = min(low[nod], low[G[nod][i]]);
if(low[G[nod][i]] >= dfn[nod])
golire_stiva(G[nod][i], nod);
}
else
{
low[nod] = min(low[nod], dfn[G[nod][i]]);
}
}
}
void out()
{
ofstream g("biconex.out");
g << nrcmp << '\n';
for(int i=1; i<=nrcmp; ++i)
{
int dim = componente[i].size();
sort(componente[i].begin(), componente[i].end());
componente[i].erase(unique(componente[i].begin(), componente[i].end()), componente[i].end());
for(int j=0; j<componente[i].size(); ++j)
g << componente[i][j] << ' ';
g << '\n';
}
g.close();
}
int main()
{
read();
dfs(1, 0);
out();
return 0;
}