Cod sursa(job #2562748)

Utilizator flee123Flee Bringa flee123 Data 29 februarie 2020 17:47:36
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.03 kb
#include <bits/stdc++.h>
#define nmax 100005
#define pb push_back
using namespace std;

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

int n, m, indexat, depth[nmax], st[nmax], ss, numscc;
vector <int> graph[nmax];
vector <int> ctc[nmax];
bitset <nmax> vizat;

int strongcon(int v, int indexat)
{
    depth[v] = indexat;
    st[ss++] = v;
    vizat[v] = 1;
    unsigned i, len;
    len = graph[v].size();
    int vecin;
    for(i = 0; i < len; i++)
    {
        vecin = graph[v][i];
        if(depth[vecin] == 0)
            depth[v] = min(depth[v], strongcon(vecin, indexat + 1));
        else if(vizat[vecin])
            depth[v] = min(depth[v], depth[vecin]);
    }
    if(depth[v] == indexat)
    {
        do{
            vecin = st[--ss];
            vizat[vecin] = false;
            ctc[numscc].pb(vecin);
        }while(vecin != v);
        numscc++;
    }
    return depth[v];
}

int main()
{
    int i, x, y;
    fin >> n >> m;
    for(i = 0; i < m; i++)
        fin >> x >> y, graph[x].pb(y);
    for(i = 1; i <= n; i++)
        if(depth[i] == 0)
            strongcon(i, 1);
    fout << numscc << '\n';
    for(i = 0; i < numscc; i++)
    {
        x = ctc[i].size();
        for(y = x - 1; y >= 0; y--)
            fout << ctc[i][y] << ' ';
        fout << '\n';
    }
    return 0;
}

/*
Mirela_Magdalena
Catrina Mirela
#define NMAX 100005

#include <iostream>

#include <fstream>

#include <stack>

#include <vector>

using namespace std;



ifstream f("ctc.in");

ofstream g("ctc.out");



int index = 1;

int n, m, nrc;

int isInStack[NMAX], viz[NMAX], lowlink[NMAX], idx[NMAX];

vector<int> graph[NMAX];

vector<int> CC[NMAX];

stack<int> S;



void read()

{

    int x, y;



    f>>n>>m;

    for(int i = 0; i < m; ++i)

    {

        f>>x>>y;

        graph[x].push_back(y);

    }

}





void addCC()

{

    nrc++;

    int top;

    do{

        top = S.top();

        CC[nrc].push_back(top);

        S.pop();

        isInStack[top] = 0;

    }while(lowlink[top] != idx[top]);



}









void solve(int nod)

{

    S.push(nod);

    isInStack[nod] = 1;

    viz[nod] = 1;

    idx[nod] = index;

    lowlink[nod] = index;

    index ++;



    for(auto &v:graph[nod])

    {

        if(viz[v] == 0)

        {

            solve(v);

            lowlink[nod] = min(lowlink[nod], lowlink[v]);

        }

        else{

            if(isInStack[v] == 1)

                lowlink[nod] = min(lowlink[nod], lowlink[v]);

        }

    }



    if(lowlink[nod] == idx[nod])

    {

        addCC();

    }



}









void tarjan()

{

//    init();



    for(int i = 1; i <= n; ++i)

        if(viz[i] == 0)

            solve(i);

}





void write()

{

    g<<nrc<<"\n";

    for(int i = 1; i <= nrc; ++i)

    {

        for(auto &v:CC[i])

            g<<v<<" ";

        g<<'\n';

    }

}









int main()

{

    read();

    tarjan();

    write();

    return 0;

}
*/

/*
	Ionut28
#include <bits/stdc++.h>

using namespace std;



ifstream fin("ctc.in");

ofstream fout("ctc.out");



const int nmax = 100005;



int n, m, nrctc;

stack < int > S;

int viz[nmax];

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



void read()

{

    fin >> n >> m;

    for(int i = 1; i <= m; ++i)

    {

        int x, y;

        fin >> x >> y;

        G[x].push_back(y);

        GT[y].push_back(x);



    }

}



void DFS1(int nod)

{

    viz[nod] = 1;

    for(unsigned int i = 0; i < G[nod].size(); ++i)

    {

        int vecin = G[nod][i];

        if(!viz[vecin])

            DFS1(vecin);

    }

    S.push(nod);

}



void DFS2(int nod)

{

    viz[nod] = 2;

    CTC[nrctc].push_back(nod);

    for(unsigned int i = 0; i < GT[nod].size(); ++i)

    {

        int vecin = GT[nod][i];

        if(viz[vecin] == 1)

            DFS2(vecin);

    }

}



void solve()

{

    for(int i = 1; i <= n; ++i)

        if(!viz[i])

            DFS1(i);

    while(!S.empty())

    {

        int nod = S.top();

        if(viz[nod] == 1)

        {

            nrctc++;

            DFS2(nod);

        }

        S.pop();

    }

}



void afisare()

{

    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();

    afisare();

    return 0;

}*/
/*
AlbertUngureanu
#include <bits/stdc++.h>



using namespace std;



ifstream fin("ctc.in");

ofstream fout("ctc.out");



int N, M, nR;

bool Viz[100005],VizT[100005];

vector<int>Ad[100005],AdT[100005],Ord,TareCon[100005];



void citire()

{

    int x,y;

    fin>>N>>M;

    for(int i=1;i<=M;i++)

    {

        fin>>x>>y;

        Ad[x].push_back(y);

        AdT[y].push_back(x);

    }

}



void sortareTopologica(int x)

{

    Viz[x]=1;

    for(unsigned i=0;i<Ad[x].size();i++)

        if(!Viz[Ad[x][i]])

            sortareTopologica(Ad[x][i]);

    Ord.push_back(x);

}



void DFS(int x)

{

    VizT[x]=1;

    TareCon[nR].push_back(x);

    for(unsigned i=0;i<AdT[x].size();i++)

        if(!VizT[AdT[x][i]])

            DFS(AdT[x][i]);

}



int main()

{

    citire();

    for(int i=1;i<=N;i++)

        if(!Viz[i])

            sortareTopologica(i);

    for(int x=(int)Ord.size()-1;x>=0;x--)

        if(!VizT[Ord[x]])

        {

            nR++;

            DFS(Ord[x]);

        }

    fout<<nR<<'\n';

    for(int i=1;i<=nR;i++)

    {

        for(unsigned j=0;j<TareCon[i].size();j++)

            fout<<TareCon[i][j]<<" ";

        fout<<'\n';

    }

    return 0;

}
*/