Cod sursa(job #1179448)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 28 aprilie 2014 18:54:26
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include<fstream>
#include<vector>
#include<bitset>
#define Next (++pos==100)?(fin.read(Buffer,100),pos = 0):0
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,pos,str;
vector<int>vin[100005];
vector<int>pleaca[100005];
vector<int>componente[100005];
bitset<100005>viza;
bitset<100005>vizb;
bitset<100005>viz;
char Buffer[100];

inline void Read(int &x)
{
    while(Buffer[pos]<'0' || '9'<Buffer[pos])
        Next;
    x = 0;
    while('0'<=Buffer[pos] && Buffer[pos]<='9')
    {
        x = x*10 +Buffer[pos]-'0';
        Next;
    }
}

inline void Citire()
{
    int i,x,y;
    fin.read(Buffer,100);
    Read(n);Read(m);
    for (i=1;i<=m;i++)
        {
            Read(x);Read(y);
            pleaca[x].push_back(y);
            vin[y].push_back(x);
        }
}

inline void DFSa(int x)
{
    int i,len;
    viza[x]=1;
    len=pleaca[x].size();
    for (i=0;i<len;i++)
        if (!viza[pleaca[x][i]])
            DFSa(pleaca[x][i]);
}

inline void DFSb(int x)
{
    int i,len;
    vizb[x]=1;
    len=vin[x].size();
    for (i=0;i<len;i++)
        if (!vizb[vin[x][i]])
            DFSb(vin[x][i]);
}

inline void Rezolva()
{
    int i,j;
    for (i=1;i<=n;i++)
        if (!viz[i])
            {
                for (j=1;j<=n;j++) viza[j]=vizb[j]=0;
                DFSa(i);
                DFSb(i);
                str++;
                for (j=1;j<=n;j++)
                    if (viza[j] && vizb[j])
                        {
                            viz[j]=1;
                            componente[str].push_back(j);
                        }

            }
}

inline void Afisare()
{
    int i,j,len;
    fout<<str<<"\n";
    for (i=1;i<=str;i++)
        {
            len=componente[i].size();
            for (j=0;j<len;j++)
                fout<<componente[i][j]<<" ";
            fout<<"\n";
        }
}

int main()
{
    Citire();
    Rezolva();
    Afisare();
    return 0;
}