Cod sursa(job #2105242)

Utilizator andrei13Paval Andrei andrei13 Data 12 ianuarie 2018 21:35:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#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;
}