Cod sursa(job #1930273)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 18 martie 2017 17:54:39
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#define nmax 100005

using namespace std;

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

int n,m,st[nmax],vf,vf2;
bool viz1[nmax],viz2[nmax];
vector<int> g[nmax],gt[nmax],scc[nmax];

void read()
{
    int x,y;
    fin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}

void dfs1(int k)
{
    viz1[k] = 1;
    for(vector<int>::iterator ii = g[k].begin();ii != g[k].end();++ii)
        if(!viz1[*ii])
            dfs1(*ii);
    st[++vf] = k;
}

void dfs2(int k)
{
    viz2[k] = 1;
    scc[vf2].push_back(k);
    for(vector<int>::iterator ii = g[k].begin();ii != g[k].end();++ii)
        if(!viz2[*ii])
            dfs2(*ii);
}

int main()
{
    read();
    for(int i = 1;i <= n;i++)
        if(!viz1[i])
            dfs1(i);
    for(int i = 1;i <= vf;i++)
        if(!viz2[st[i]])
        {
            dfs2(st[i]);
            vf2++;
        }
    fout << vf2 << "\n";
    for(int i = 0;i < vf2;i++)
    {
        for(vector<int>::iterator ii = scc[i].begin();ii != scc[i].end();++ii)
        {
            fout << *ii << " ";
        }
        fout << "\n";
    }
    return 0;
}