Cod sursa(job #1515657)

Utilizator hegedusPaul Hegedus hegedus Data 1 noiembrie 2015 23:31:04
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
using namespace std;

bool boolbreak,viz[1000],a[1000][1000],t[1000][1000];
unsigned short v[1000],i,j,k,n,m,x,y,q,grup[1000];

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;
        t[y][x]=1;
    }
}

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

void write()
{
    g<<q<<endl;
    for(i=1;i<=n;i++)
    {
        if (!viz[grup[i]])
        {
            viz[grup[i]]=1;
            for (j=i;j<=n;j++)
                if(grup[j]==grup[i])
                    g<<j<<" ";
            g<<endl;
        }
    }
}

int main()
{
    read();
    for(i=1;i<=n;i++)
        if(grup[i]==0)
        {
            deep_search(i,a);
            deep_search(i,t);
            ++q;
            for(j=1;j<=n;j++)
                if(a[0][j] && t[0][j] && grup[j]==0)
                    grup[j]=q;
            for(j=1;j<=n;j++)
            {
                a[0][j]=0;
                t[0][j]=0;
            }
        }
    write();
    g.close();
    return 0;
}