Cod sursa(job #1837749)

Utilizator alexionpopescuPopescu Ion Alexandru alexionpopescu Data 30 decembrie 2016 13:37:05
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include<vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> a[20001],b[20001];
int n,m,p[10001],s[10001],nrt;
void cit(){
    int i,j,h;
    fin>>n>>m;
    for(h=1;h<=m;h++){
        fin>>i>>j;
        a[i].push_back(j);
        b[j].push_back(i);
    }
    fin.close();
}
void dfss(int k){
    int i;
    s[k]=nrt;
    for(i=0;i<a[k].size();i++)
        if(s[a[k][i]]==0)
            dfss(a[k][i]);
}
void dfsp(int k){
    int i;
    p[k]=nrt;
    for(i=0;i<b[k].size();i++)
        if(p[b[k][i]]==0)
            dfsp(b[k][i]);
}
void rez(){
    int i,j;
    for(i=1;i<=n;i++)
        if(s[i]==0){
            nrt++;
            dfss(i);dfsp(i);
            for(j=1;j<=n;j++)
                if(s[j]==0||p[j]==0)
                    s[j]=p[j]=0;
        }
}
void afis(){
    int i,j;
    fout<<nrt<<'\n';
    for(i=1;i<=nrt;i++){
        for(j=1;j<=n;j++)
            if(s[j]==i)
                fout<<j<<" ";
        fout<<'\n';
    }
    fout.close();
}
int main(){
    cit();
    rez();
    afis();
    return 0;
}