Pagini recente » Borderou de evaluare (job #425773) | Borderou de evaluare (job #261435) | Borderou de evaluare (job #3233597) | Cod sursa (job #1713728)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int MAXN = 100005;
int n, m, x, y, nrComp = 0;
int hh[MAXN],viz[MAXN];
vector < int > graph [MAXN];
stack < int > stiva;
vector<int> v[MAXN];
void scoate_componenta(int nod)
{
++nrComp;
while (stiva.top() != nod)
{
v[nrComp].push_back(stiva.top());
stiva.pop();
}
v[nrComp].push_back(stiva.top());
stiva.pop();
}
void dfs (int nod, int depth)
{
hh[nod] = depth;
viz[nod] = 1;
stiva.push(nod);
int how_high = depth;
for (auto it : graph[nod] )
{
if (viz[it])
how_high = min(how_high, hh[it]);
else
{
dfs(it, depth + 1);
how_high = min (how_high, hh[it]);
if (hh[it] == depth)
{
scoate_componenta(it);
v[nrComp].push_back(nod);
}
}
}
hh[nod] = how_high;
}
int main()
{
fin >> n >> m;
while(m--)
{
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for(int i=1; i<=n; i++)
{
if(!viz[i])
dfs(i, 0);
}
fout<<nrComp<<endl;
for(int i=1; i<=nrComp; i++)
{
reverse(v[i].begin(), v[i].end());
for(auto it: v[i])
fout<<it<<" ";
fout<<"\n";
}
}