Cod sursa(job #1511590)

Utilizator hegedusPaul Hegedus hegedus Data 26 octombrie 2015 22:06:58
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
using namespace std;

bool a[10000][10000],viz[10000],wiz[10000],boolbreak;
unsigned short v[10000],w[10000],i,j,k,n,m,x,y,i1,ala;

ifstream f("ctc.in");
ofstream g("ctc.out");

void read()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x][y]=1;
    }
}

void deep_search(int i)
{
    viz[i]=1; v[1]=i; k=1;
    do
    {
        boolbreak=0;
        for(j=1;j<=n;j++)
        {
            if (a[v[k]][j] && !viz[j])
            {
                viz[j]=1;
                v[++k]=j;
                a[i][j]=1;
                boolbreak=1;
            }
            if (boolbreak) break;
        }
        if(j>n) --k;
    }while(k>0);
}

int main()
{
    read();
    for(i=1;i<=n;i++)
    {
        deep_search(i);
        if(i<n) for(j=1;j<=n;j++) viz[j]=0;
    }
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++) cout<<a[i][j]<<" ";
        cout<<endl;
    }*/

    k=n;
    for(i=1;i<=n;i++) w[i]=i;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j] && a[j][i] && w[i]!=w[j])
            {
                --k;
                ala=w[j];
                for(i1=1;i1<=n;i1++)
                    if(w[i1]==ala) w[i1]=w[i];
            }

    g<<k<<endl;
    for(i=1;i<=n;i++)
        if (!wiz[w[i]])
        {
            wiz[w[i]]=1;
            for(j=i;j<=n;j++)
                if (w[j]==w[i]) g<<j<<" ";
            g<<endl;
        }
    g.close();
    return 0;
}