Cod sursa(job #2012528)

Utilizator rangal3Tudor Anastasiei rangal3 Data 18 august 2017 23:15:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
#define in "ctc.in"
#define out "ctc.out"
#define N 100003
using namespace std;

ifstream fin(in);
ofstream fout(out);

int n,m,x,y;
stack < int > st;
vector < int > g[N],gt[N];
int nctc;
vector < int > sol[N];
bitset <N> f;

void read_input()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}

inline void DFS(int nod)
{
    f[nod] = 1;
    vector < int >::iterator it;

    for(it = g[nod].begin(); it != g[nod].end(); ++it)
        if(!f[*it])
        {
            int x = *it;
            DFS(x);
        }

    st.push(nod);
}

inline void DFSt(int nod)
{
    sol[nctc].push_back(nod);
    f[nod] = 1;

    vector < int >::iterator it;

    for(it = gt[nod].begin(); it != gt[nod].end(); ++it)
        if(!f[*it]) DFSt(*it);
}

void solve()
{
    for(int i=1; i<=n; ++i)
        if(!f[i])
            DFS(i);

    f.reset();

    while(!st.empty())
    {
        int x = st.top();
        if(!f[x])
        {
            DFSt(x);
            ++nctc;
        }
        st.pop();
    }
}

void write_output()
{
    fout<<nctc<<"\n";
    for(int i=0; i<nctc; ++i)
    {
        vector < int >::iterator it;
        for(it = sol[i].begin(); it!= sol[i].end(); ++it)
            fout<<*it<<" ";
        fout<<"\n";
    }
}

int main()
{
    read_input();

    solve();

    write_output();

    fin.close(); fout.close();
    return 0;
}