Cod sursa(job #925455)

Utilizator alexandrul_21Niculescu Mihai alexandrul_21 Data 24 martie 2013 15:57:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_N 100000
ofstream fout("biconex.out");
struct nod
{
    int nr,nr2;
    nod *next;
}*First[MAX_N+5],*List[MAX_N+5],*Stack;
int N,M,NRC;
int Niv[MAX_N],NivMin[MAX_N];
void Insert(int x,int y,nod *p[MAX_N])
{
    nod *q=new nod;
    q->nr=y;
    q->next=p[x];
    p[x]=q;
}
void Read()
{
    ifstream fin("biconex.in");
    fin>>N>>M;
    int i,x,y;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        Insert(x,y,First);
        Insert(y,x,First);
    }
    fin.close();
}
void PutInStack(int nr,int nr2)
{
    nod *q=new nod;
    q->nr=nr;
    q->nr2=nr2;
    q->next=Stack;
    Stack=q;
}
void AddComp(int k)
{
    int nr,nr2;
    nod *q;
    NRC++;
    for(q=Stack;q;)
    {
        nr=q->nr;
        nr2=q->nr2;
        Stack=Stack->next;
        delete q;
        q=Stack;
        Insert(NRC,nr2,List);
        if(nr==k)
            break;
    }
    Insert(NRC,nr,List);
}
void WriteComp(nod *p)
{
    if(p)
    {
        fout<<p->nr<<" ";
        WriteComp(p->next);
    }
    else
        fout<<'\n';
}
void Write()
{
    int i;
    fout<<NRC<<'\n';
    for(i=1;i<=NRC;i++)
    {
        WriteComp(List[i]);
    }
}
void DF(int k,int t,int niv)
{
    Niv[k]=NivMin[k]=niv;
    nod *q;
    int cur;
    for(q=First[k];q;q=q->next)
    {
        cur=q->nr;
        if(cur==t)
            continue;
        if(Niv[cur]==0)
        {
            PutInStack(k,cur);
            DF(cur,k,niv+1);
            if(Niv[k]<=NivMin[cur])
            {
                AddComp(k);
            }
            if(NivMin[k]>NivMin[cur])
                NivMin[k]=NivMin[cur];
        }
        else
            if(NivMin[k]>Niv[cur])
                NivMin[k]=Niv[cur];

    }
}
int main()
{
    Read();
    DF(1,0,1);
    Write();
    return 0;
}