Cod sursa(job #1689951)

Utilizator lupvasileLup Vasile lupvasile Data 14 aprilie 2016 17:33:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
#define cout fout
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#else
ifstream fin("date.in");
#endif // INFOARENA

/// ///////////////////////////////////////////

void read();

#define nmax 100010
#define inf 0x3f3f3f3f

vector<int> G[nmax],G_t[nmax];
vector<vector<int>> ctc;
bool viz[nmax];
int st[nmax],n;

void dfs_1(int nod)
{
    viz[nod]=1;

    for(auto vec:G[nod])
        if(!viz[vec]) dfs_1(vec);

    st[++st[0]]=nod;
}

void dfs_2(int nod)
{
    viz[nod]=1;

    ctc.back().push_back(nod);

    for(auto vec:G_t[nod])
        if(!viz[vec]) dfs_2(vec);
}


int main()
{
    read();

    for(int i=1;i<=n;++i)
        if(!viz[i]) dfs_1(i);

    memset(viz,0,sizeof viz);
    for(;st[0];--st[0])
        if(!viz[st[st[0]]])
        {
            ctc.push_back(vector<int>());
            dfs_2(st[st[0]]);
        }

    cout<<ctc.size()<<'\n';
    for(auto &comp:ctc)
    {
        for(auto &it:comp) cout<<it<<' ';
        cout<<'\n';
    }
}
void read()
{
    int x,y,c,m;
    fin>>n>>m;
    for(;m;--m)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G_t[y].push_back(x);
    }
}