Cod sursa(job #2203652)

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

using namespace std;

#define NMAX 100001

bool visited[NMAX];
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[*it])
            dfsp(*it);
}

int main()
{
    memset(visited, false, sizeof(visited));
    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();
    
    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();
}