Pagini recente » Cod sursa (job #3258104) | Cod sursa (job #3234331) | Cod sursa (job #2566431) | Cod sursa (job #2988596) | Cod sursa (job #1165584)
#include <fstream>
#include <stack>
#include <vector>
#include <cassert>
#include <algorithm>
#define NM 100010
using namespace std;
ifstream f("santa.in");
ofstream g("santa.out");
int N, M, K;
vector<int> G[NM];
vector<int> Component[NM];
int Level[NM], LowPoint[NM];
stack< pair<int, int> > S;
void DF (int node, int father)
{
LowPoint[node]=Level[node];
for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
{
if (*it==father)
continue;
if (Level[*it]==0)
{
Level[*it]=Level[node]+1;
S.push(make_pair(node, *it));
DF(*it, node);
LowPoint[node]=min(LowPoint[node], LowPoint[*it]);
if (LowPoint[*it]>=Level[node]) // am punct de articulatie
{
K++;
for (; !S.empty() && S.top()!=make_pair(node, *it); S.pop())
{
Component[K].push_back(S.top().first);
Component[K].push_back(S.top().second);
}
if (!S.empty() && S.top()==make_pair(node, *it))
{
Component[K].push_back(S.top().first);
Component[K].push_back(S.top().second);
S.pop();
}
}
}
else
LowPoint[node]=min(LowPoint[node], Level[*it]);
}
}
int main ()
{
f >> N >> M;
for (int i=1; i<=M; i++)
{
int x, y;
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i=1; i<=N; i++)
if (!Level[i])
{
Level[i]=1;
DF(i, 0);
}
g << K << '\n';
for (int i=1; i<=K; i++)
{
sort(Component[i].begin(), Component[i].end());
Component[i].erase(unique(Component[i].begin(), Component[i].end()), Component[i].end());
assert(Component[i].size()<=15);
for (vector<int>::iterator it=Component[i].begin(); it!=Component[i].end(); ++it)
g << (*it) << ' ';
g << '\n';
}
f.close();
g.close();
return 0;
}