Cod sursa(job #2284817)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 17 noiembrie 2018 16:56:32
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#define MaxN 100005
#define MaxM 200005
#define min(a, b) (a<b?a:b)
using namespace std;
struct Pair{
    int index;
    int head;
    int numb;
};
vector<Pair> S;
int Out[MaxM], *List[MaxN], N, M, i, j, c=0, Use[MaxN], V, Count, pres;
bool k;
void Read();
void DFS(int i, int p);
int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    Read();
    Pair a; a.index=a.head=a.numb=0;
    S.push_back(a);
    for(i=1; i<=N; ++i){
        if(Use[i]==0){
            k=false;
            ++c; Pair a; a.index=a.head=c; a.numb=i;
            Use[i]=c;
            S.push_back(a);
            DFS(i, c);
            if(Use[i]==S.back().head){
            ++Count;
            while(S.back().index!=i){
            Out[++V]=S.back().index;
            S.pop_back();
    }
    Out[++V]=0;
    }
        }
    }
    printf("%d\n", Count);
    for(i=1; i<=V; ++i)
        if(Out[i]==0)printf("\n");
        else printf("%d ", Out[i]);
    return 0;
}
void Read(){
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i){
        List[i]=(int *)realloc(List[i], sizeof(int));
        List[i][0]=0;
    }
    for(i=1; i<=M; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        ++List[x][0];
        List[x]=(int *)realloc(List[x], (List[x][0]+1)*sizeof(int));
        List[x][List[x][0]]=y;
    }
    return;
}
void DFS(int i, int p){
    int j;
    for(j=1; j<=List[i][0]; ++j){
        if(Use[List[i][j]]==0){
            ++c; int q=c; Pair a; a.index=a.head=c;
            a.numb=List[i][j];
            Use[List[i][j]]=c;
            S.push_back(a);
            DFS(List[i][j], c);
            if(k==false)S.at(p).head=min(S.at(p).head, S.at(q).head);
            else k=false;
        }
        else S.at(p).head=min(S.at(p).head, Use[List[i][j]]);
    }
    if(Use[i]==S.at(p).head){
        ++Count;
    while(S.back().index!=Use[i]){
        Out[++V]=S.back().numb;
        S.pop_back();
        --c;
    }
    Out[++V]=S.back().numb;
    S.pop_back();
    --c;
    Out[++V]=0;
    k=true;
    }
}