Cod sursa(job #2203645)

Utilizator silviu982001Borsan Silviu silviu982001 Data 12 mai 2018 20:12:22
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <algorithm>
#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>

using namespace std;

#define NMAX 100001

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;
    for (vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
        if (!visited[*it])
            dfs(*it);
    st.push(nod);
}

void dfsp(int nod)
{
    visited[nod] = 0;
    result[ctcno].push_back(nod+1);
    for (vector<int>::iterator it = p[nod].begin(); it != p[nod].end(); ++it)
        if (visited[p[nod][*it]])
            dfsp(p[nod][*it]);
}

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++)
    {
        for(vector<int>::iterator it = result[i].begin(); it != result[i].end(); ++it)
            fout << *it << " ";
        fout << endl;
    }
    fout.close();
}