Cod sursa(job #2279497)

Utilizator aturcsaTurcsa Alexandru aturcsa Data 9 noiembrie 2018 17:05:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
bool viz[100001];
vector<int> A[100001];
vector<int> T[100001];
vector<int> rez[100001];
stack <int>Q;
int n,m,nm=0;
void dfs1(int nod)
{
    viz[nod]=1;

    vector<int> :: iterator it;
    for(it=A[nod].begin();it!=A[nod].end();it++)
        if(!viz[*it])
            dfs1(*it);
    Q.push(nod);
}
void dfs2(int nod)
{
    viz[nod]=1;
    rez[nm].push_back(nod);
    vector<int> :: iterator it;
    for(it=T[nod].begin();it!=T[nod].end();it++)
        if(!viz[*it])
            dfs2(*it);
    Q.push(nod);
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;;
        fin>>a>>b;
        A[a].push_back(b);
        T[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            dfs1(i);
    for(int i=1;i<=n;i++)
        viz[i]=0;
    while(!Q.empty())
    {
        int v;
        v=Q.top();
        Q.pop();
        if(!viz[v])
        {
            nm++;
            dfs2(v);
        }
    }
    fout<<nm<<"\n";
    for(int i=1;i<=nm;++i)
    {
        for(auto it:rez[i])
            fout<<it<<" ";
        fout<<'\n';
    }
    return 0;
}
////https://infoarena.ro/problema/ctc
//+ de studiat algoritmul lui Tarjan pentru Componente Tare Conexa
//
//
//
//#include <fstream>
//#include <vector>
//#include <stack>
//using namespace std;
//ifstream fi("ctc.in");
//ofstream fo("ctc.out");
//int N,M;
//vector <int> ADJ[100001];
//vector <int> ADJT[100001];
//vector <int> CTC[100001];
//int VIZ[100001];
//stack <int> S;
//stack <int> SS;
//int rez=0;
//
//void df(int v)
//{
//    vector <int> :: iterator it;
//    VIZ[v]=1;
//    for (it=ADJ[v].begin();it!=ADJ[v].end();it++)
//    {
//        int varf;
//        varf=(*it);
//        if (VIZ[varf]==0)
//            df(varf);
//    }
//    S.push(v);
//}
//
//void dft(int v)
//{
//    vector <int> :: iterator it;
//    VIZ[v]=1;
//    CTC[rez].push_back(v);
//    for (it=ADJT[v].begin();it!=ADJT[v].end();it++)
//    {
//        int varf;
//        varf=(*it);
//        if (VIZ[varf]==0)
//            dft(varf);
//    }
//}
//
//int main()
//{
//    fi>>N>>M;
//    for (int i=1;i<=M;i++)
//    {
//        int a,b;
//        fi>>a>>b;
//        ADJ[a].push_back(b);
//        ADJT[b].push_back(a);
//    }
//    /// se depun varfuri in stiva
//    for (int i=1;i<=N;i++)
//        if (VIZ[i]==0)
//            df(i);
//    /// se face df in graful transpus
//    /// varfurile sunt considerate in ordinea data de stiva S
//    for (int i=1;i<=N;i++)
//        VIZ[i]=0;
//    /// numarul de componente tare conexe
//
//    SS=S;
//    while (!S.empty())
//    {
//        int v;
//        v=S.top();
//        S.pop();
//        if (VIZ[v]==0)
//        {
//            rez++;
//            dft(v);
//        }
//    }
//    fo<<rez<<'\n';
//    for(int nrsol=1;nrsol<=rez;++nrsol)
//    {
//        for(auto nod:CTC[nrsol])fo<<nod<<" ";
//        fo<<'\n';
//    }
//    fi.close();
//    fo.close();
//    return 0;
//}