Cod sursa(job #1841234)

Utilizator vladisimovlad coneschi vladisimo Data 5 ianuarie 2017 14:19:05
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,a[5005][5005],nrt=0,s[5005],p[5005],m;
void cit(){
    int i,j,k,x;
    fin>>n>>m;
    for(k=1;k<=m;k++){
        fin>>i>>j;
        a[i][j]=1;
    }
}
void ads(int k){
    int i;
    s[k]=nrt;
    for(i=1;i<=n;i++)
        if(s[i]==0&&a[k][i]==1)
            ads(i);
}
void adp(int k){
    int i;
    p[k]=nrt;
    for(i=1;i<=n;i++)
        if(p[i]==0&&a[i][k]==1)
            adp(i);
}
void ctc(){
    int i,j;
    for(i=1;i<=n;i++){
        if(s[i]==0){
            nrt++;
            ads(i);adp(i);
            for(j=1;j<=n;j++)
                if(s[j]==0||p[j]==0){
                    s[j]=0;p[j]=0;}
        }
    }
}
int main()
{
    cit();nrt=0;
    ctc();
    fout<<nrt<<'\n';
    int i,j;
    for(i=1;i<=nrt;i++){
        for(j=1;j<=n;j++)
            if(s[j]==i)
                fout<<j<<" ";
    fout<<'\n';
    }
    return 0;
}