Cod sursa(job #2172830)

Utilizator anisca22Ana Baltaretu anisca22 Data 15 martie 2018 18:12:50
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#define NMAX 100005

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

int N, M, K;
int height[NMAX], jump[NMAX], inStack[NMAX];

vector <int> v[NMAX], rsp[NMAX];
stack <int> st;

void read()
{
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
    }
}
void write()
{
    fout << K << "\n";
    for (int i = 1; i <= K; i++)
    {
        vector<int>::iterator it;
        for(it = rsp[i].begin(); it != rsp[i].end(); it++)
            fout << *it << " ";
        fout << "\n";
    }
}

void ctc(int nod, int nivel)
{
    height[nod] = jump[nod] = nivel;
    st.push(nod);
    inStack[nod] = 1;
    vector <int> :: iterator it;
    for (it = v[nod].begin(); it != v[nod].end(); it++)
    {
        int nxt = *it;
        if (!height[nxt])
        {
            ctc(nxt, nivel + 1);
            jump[nod] = min(jump[nod], jump[nxt]);
        }
        else if (inStack[nxt]) jump[nod] = min(jump[nod], jump[nxt]);
    }
    if (height[nod] == jump[nod])
    {
        K++;
        while (st.top() != nod)
        {
            rsp[K].push_back(st.top());
            inStack[st.top()] = 0;
            st.pop();
        }
        rsp[K].push_back(st.top());
        inStack[st.top()] = 0;
        st.pop();
    }
}

int main()
{
    read();
    for (int i = 1; i <= N; i++)
        if (!height[i])
            ctc(i, 1);
    write();
    return 0;
}