Pagini recente » Cod sursa (job #3249538) | Cod sursa (job #2384524) | Cod sursa (job #2887759) | Cod sursa (job #249059) | Cod sursa (job #2372766)
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("meh.in");
ofstream g ("meh.out");
int t1[100010], t2[100010], st[100010];
int nr, n, m, nr_componente, k, x, y;
bool viz[100010];
vector<int> sol[100010], G[100010];
void dfs (int x)
{
nr++;
t1[x]=t2[x]=nr;
viz[x]=1;
st[++k]=x;
for (int i=0; i<G[x].size(); i++)
{
if (!viz[G[x][i]])
{
int y=k;
dfs(G[x][i]);
t2[x]=min(t2[x], t2[G[x][i]]);
if (t2[G[x][i]]>=t1[x])
{
nr_componente++;
while (k>y)
{
sol[nr_componente].push_back(st[k]);
k--;
}
sol[nr_componente].push_back(x);
}
}
else t2[x]=min(t2[x], t1[G[x][i]]);
}
}
int main ()
{
f >> n >> m;
for (int i=1; i<=m; i++)
{
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
g << nr_componente << '\n';
for (int i=1; i<=nr_componente; i++)
{
for (int j=0; j<sol[i].size(); j++)
g << sol[i][j] << " ";
g << '\n';
}
return 0;
}