Pagini recente » Cod sursa (job #2277329) | Cod sursa (job #1868426) | Cod sursa (job #1293131) | Cod sursa (job #1464896) | Cod sursa (job #2105242)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream f("johnie.in");
ofstream g("johnie.out");
int n,m,nr;
struct node
{
int inf;
node* leg;
};
node *list[50005];
node *rez[50005];
stack <int> st;
void add(int a,int b)
{
node *p;
p=new node;
p->inf=b;
p->leg=list[a];
list[a]=p;
}
void del(int a,int b)
{
node *p=list[a],*r=NULL;
while(p->inf!=b)
r=p,p=p->leg;
if(r)
r->leg=p->leg;
else list[a]=p->leg;
}
void add2(int v)
{
node *p=new node;
p->inf=v;
p->leg=rez[nr]->leg;
rez[nr]->leg=p;
++rez[nr]->inf;
}
int main()
{
int x,y;
f>>n>>m;
while(m)
{
f>>x>>y;
add(x,y);
add(y,x);
--m;
}
for(int i=1; i<=n; i++)
if(!(!list[i]))
{
nr++;
int v=i;
st.push(v);
while(!st.empty())
{
int nc=st.top();
if(list[nc])
{
st.push(list[nc]->inf);
list[nc]=list[nc]->leg;
del(st.top(),nc);
}
else
{
add2(st.top());
st.pop();
}
}
}
g<<nr<<endl;
for(int i=1; i<=nr; ++i)
{
g<<rez[i]->inf;
node*p=rez[i]->leg;
while(p)
{
g<<p->inf<<' ';
p=p->leg;
}
}
return 0;
}