Pagini recente » Cod sursa (job #1196209) | Cod sursa (job #1267297) | Cod sursa (job #517452) | Cod sursa (job #152781) | Cod sursa (job #1833106)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n, m;
vector<int> vecini[100005];
int viz[100005];
int nivel[100005];
int sus[100005];
stack<int> S;
int nrComponente = 0;
vector<vector<int> > sol;
void citire()
{
scanf("%d %d", &n, &m);
int tmp1, tmp2;
for(int i = 0; i < m; i++)
{
scanf("%d %d", &tmp1, &tmp2);
tmp1--;
tmp2--;
vecini[tmp1].push_back(tmp2);
vecini[tmp2].push_back(tmp1);
}
}
void eliminare(int nod, int tata)
{
vector<int> tmp;
tmp.push_back(tata);
while(S.top() != nod)
{
tmp.push_back(S.top());
S.pop();
}
tmp.push_back(nod);
S.pop();
sol.push_back(tmp);
}
void dfs(int x, int tata)
{
viz[x] = true;
nivel[x] = nivel[tata] + 1;
sus[x] = nivel[x];
for(int i = 0; i < vecini[x].size(); i++)
{
if(vecini[x][i] == tata)
{
continue;
}
if(viz[vecini[x][i]] == false)
{
S.push(vecini[x][i]);
dfs(vecini[x][i], x);
sus[x] = min(sus[x], sus[vecini[x][i]]);
if(nivel[x] <= sus[vecini[x][i]])
{
nrComponente++;
eliminare(vecini[x][i], x);
}
}
else
{
sus[x] = min(sus[x], nivel[vecini[x][i]]);
}
}
}
void afisare()
{
printf("%d\n", nrComponente);
for(int i = 0; i < sol.size(); i++)
{
for(int j = 0; j < sol[i].size(); j++)
{
printf("%d ", sol[i][j] + 1);
}
printf("\n");
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
citire();
S.push(0);
dfs(0, -1);
afisare();
return 0;
}