Cod sursa(job #2810593)

Utilizator elisaioanamercasElisabeta-Ioana Mercas elisaioanamercas Data 29 noiembrie 2021 19:23:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.89 kb
// // #include <bits/stdc++.h>
// // #define camMult 100000
// // using namespace std;
// // ifstream fin ("ctc.in");
// // ofstream fout ("ctc.out");
// // vector <int> G[camMult], Gt[camMult], result[camMult];
// // stack <int> S;
// // // bitset <camMult> viz;
// // int n, m, ctc, viz[camMult];
// // void read()
// // {
// //     fin>>n>>m;
// //     for(int i=1; i<=m; i++)
// //     {
// //         int x,y;
// //         fin>>x>>y;
// //         G[x].push_back(y);//construim graful G
// //         Gt[y].push_back(x);//contruim transpusa lui G
// //     }
// // }
// // void dfs(int nod)
// // {
// //     viz[nod]=1;
// //     ///zona 1
// //     for(int i:G[nod]){
// //         ///zona 2
// //         int Vecin=G[nod][i];
// //         if(!viz[Vecin])
// //             dfs(Vecin);
// //         //zona 3
// //     }
// //     S.push(nod);
// //     //zona 4
// // }
// // void dfst(int nod)
// // {
// //     viz[nod]=2;//de ce 2?
// //     result[ctc].push_back(nod);
// // }
// // void Solve()
// // {
// //     for(int i=1; i<=n; i++)
// //         if(viz[i]==0)
// //             dfs(i);
// //     while(!S.empty()){
// //         int Nod=S.top();
// //         cout<<Nod<<" ";//in consola!
// //         if(viz[Nod]==1)//daca am vizitat deja nodul
// //             ctc++, dfst(Nod);
// //         S.pop();
// //     }
// // }
// // void print()
// // {
// //     fout<<ctc<<'\n';
// //     for(int i=1; i<=ctc; i++)
// //         for(int j: result[i])
// //             fout<<result[i][j]<<" ";
// //     fout<<'\n';
// // }
// // int main()
// // {
// //     read();
// //     Solve();
// //     print();
// //     fout.close();
// //     return 0;
// // }
// #include <bits/stdc++.h>
// #define camMult 100000
// using namespace std;
// ifstream fin ("ctc.in");
// ofstream fout ("ctc.out");
// stack < int > S;
// vector<int> G[camMult],Gt[camMult],result[camMult];
// int N, M, ctc;
// int beenThere[camMult];
// void Read()
// {
//     fin >> N >> M;
//     for(int i = 1; i <= M; i++)
//     {
//         int x,y;
//         fin >> x >> y;
//         G[x].push_back(y); // Construim graful G
//         Gt[y].push_back(x); // Construim transpusa grafului G
//     }
// }
// void dfs(int Nod)
// {
//     beenThere[Nod] = 1;
//     for(unsigned int i=1; i<=G[Nod].size();i++) {
//         int Vecin = G[Nod][i];
//         if(!beenThere[Vecin])
//             dfs(Vecin);
//     }
//     S.push(Nod);
// }
// void dfst(int Nod)
// {
//     beenThere[Nod] = 2;
//     result[ctc].push_back(Nod);
//     for(unsigned int i=1; i<=Gt[Nod].size();i++) {
//         int Vecin = Gt[Nod][i];
//         if(beenThere[Vecin]==1)
//             dfst(Vecin);
//     }
// }
// void Solve()
// {
//     for(int i=1;i<=N;i++)
//         if(!beenThere[i])
//             dfs(i);
//     while(!S.empty()) {
//         int Nod = S.top();
//         cout << Nod << " ";
//         if (beenThere[Nod] == 1) {
//             ctc++;
//             dfst(Nod);
//         }
//         S.pop();
//     }
// }
// void Print()
// {
//     fout << ctc <<"\n";
//     for(int i = 1; i <= ctc; i++) {
//         for(int j: result[i])
//             fout << result[i][j] <<" ";
//         fout<<"\n";
//     }
// }
// int main()
// {
//     Read();
//     Solve();
//     Print();
//     return 0;
// }
#include    <fstream>
#include    <iostream>
#include    <vector>
#include    <stack>

#define NMax 100005

using namespace std;

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

stack < int > S;

vector<int> G[NMax],GT[NMax],CTC[NMax];

int N, M, NrCTC;
int beenThere[NMax];

void Read()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x,y;
        fin >> x >> y;
        G[x].push_back(y); // Construim graful G
        GT[y].push_back(x); // Construim transpusa grafului G
    }
}

void DFSP(int Nod)
{
    beenThere[Nod] = 1;
    for( int i=0; i<G[Nod].size();i++) {
        int Vecin = G[Nod][i];

        if(!beenThere[Vecin])
            DFSP(Vecin);
    }
    S.push(Nod);
}

void DFSM(int Nod)
{
    beenThere[Nod] = 2;
    CTC[NrCTC].push_back(Nod);

    for(int i=0; i<GT[Nod].size();i++) {
        int Vecin = GT[Nod][i];

        if(beenThere[Vecin]==1)
            DFSM(Vecin);
    }
}

void Solve()
{
    for(int i=1;i<=N;i++)
        if(!beenThere[i])
            DFSP(i);

    while(!S.empty()) {
        int Nod = S.top();
        cout << Nod << " ";
        if (beenThere[Nod] == 1) {
            NrCTC++;
            DFSM(Nod);
        }
        S.pop();
    }
}

void Print()
{
    fout << NrCTC <<"\n";

    for(int i = 1; i <= NrCTC; i++) {
        for(unsigned int j = 0; j < CTC[i].size(); j++)
            fout << CTC[i][j] <<" ";
        fout<<"\n";
    }
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}