Cod sursa(job #2203695)

Utilizator silviu982001Borsan Silviu silviu982001 Data 12 mai 2018 21:37:59
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>

using namespace std;

#define NMAX 100002

bitset<NMAX> visited;
vector<int> v[NMAX], p[NMAX], result[NMAX];
stack<int> st;
int n,m, ctcno;

void dfs(int nod)
{
    visited[nod] = 1;
    size_t sz = v[nod].size();
    for (int i = 0; i < sz; i++)
        if (!visited[v[nod][i]])
            dfs(v[nod][i]);
    st.push(nod);
}

void dfsp(int nod)
{
    visited[nod] = 0;
    size_t sz = p[nod].size();
    result[ctcno].push_back(nod+1);
    for (int i = 0; i < sz; i++)
        if (visited[p[nod][i]])
            dfsp(p[nod][i]);
}

int main()
{
    ctcno = 0;
    fstream fin("ctc.in", fstream::in);
    fin >> n >> m;
    int x, y;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y;
        --x;
        --y;
        v[x].push_back(y);
        p[y].push_back(x);
    }
    fin.close();
    visited.reset();
    
    for (int i = 0; i < n; i++)
        if (!visited[i])
            dfs(i);
    
    while (!st.empty())
    {
        int nod = st.top();
        st.pop();
        if (visited[nod])
        {
            dfsp(nod);
            ++ctcno;
        }
    }
    
    fstream fout("ctc.out", fstream::out);
    fout << ctcno << endl;
    for (int i = 0; i<ctcno;i++)
    {
        size_t sz = result[i].size();
        for(int j = 0; j < sz; j++)
            fout << result[i][j] << " ";
        fout << endl;
    }
    fout.close();
}