Pagini recente » Cod sursa (job #616499) | Cod sursa (job #2767516) | Cod sursa (job #2570410) | Cod sursa (job #2635765) | Cod sursa (job #1677796)
# include <cstdio>
# include <vector>
# include <stack>
# include <algorithm>
using namespace std;
FILE *f = freopen("biconex.in", "r", stdin);
FILE *g = freopen("biconex.out", "w", stdout);
const int N_MAX = 100001;
vector <int> G[N_MAX];
stack <pair<int, int>> stiva;
vector <int> componente[N_MAX];
int nivel[N_MAX];
int dp[N_MAX];
int total, n, m;
void read()
{
scanf("%d %d", &n, &m);
for (int i=1; i<=m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for (int i=1; i<=n; i++)
nivel[i] = -2;
}
void add_comp_biconexa(int finish1, int finish2)
{
pair <int, int> current = stiva.top();
total ++;
componente[total].push_back(current.first);
componente[total].push_back(current.second);
while (current.first != finish1 && current.second != finish2)
{
stiva.pop();
current = stiva.top();
componente[total].push_back(current.first);
componente[total].push_back(current.second);
}
stiva.pop();
}
void dfs(int nod, int niv)
{
dp[nod] = niv;
nivel[nod] = niv;
for (int i : G[nod])
{
if (nivel[i] + 1 == nivel[nod]) /// tata
continue;
if (!dp[i]) /// fiu din subarbore
{
stiva.push(make_pair(nod, i));
dfs(i, niv + 1);
dp[nod] = min(dp[nod], dp[i]);
if (dp[i] >= nivel[nod]) /// nod este punct de articulatie / critic
add_comp_biconexa(nod, i); /// adaugam pana la muchia nod - i inclusiv
}
else
dp[nod] = min(dp[nod], dp[i]); /// muchie de intoarcere
}
}
void write()
{
printf("%d\n", total);
for (int i=1; i<=total; i++)
{
sort(componente[i].begin(), componente[i].end());
componente[i].resize(unique(componente[i].begin(), componente[i].end()) - componente[i].begin());
for (int nod : componente[i])
printf("%d ", nod);
printf("\n");
}
}
int main()
{
read();
dfs(1, 1);
write();
return 0;
}