Cod sursa(job #1378496)

Utilizator radarobertRada Robert Gabriel radarobert Data 6 martie 2015 12:34:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

const int MAXN = 100002;
struct V{int index; int lowlink;};

vector<int> g[MAXN];
stack<int> st;
V v[MAXN];
bool in_stack[MAXN];
bool new_line[MAXN];
int sol[MAXN];
int nr_sol = 0;
int index = 0;

inline int Min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}

void scc(int x)
{
    in_stack[x] = 1;
    st.push(x);
    v[x].index = ++index;
    v[x].lowlink = index;
    for (int i = 0; i < g[x].size(); i++)
    {
        if (v[g[x][i]].index == 0)
        {
            scc(g[x][i]);
            v[x].lowlink = Min(v[x].lowlink, v[g[x][i]].lowlink);
        }
        else
            if (in_stack[g[x][i]])
                v[x].lowlink = Min(v[x].lowlink, v[g[x][i]].index);
    }
    if (v[x].index == v[x].lowlink)
    {
        ++nr_sol;
        new_line[sol[0]] = 1;
        int t;
        do
        {
            t = st.top();
            st.pop();
            sol[++sol[0]] = t;
            in_stack[t] = 0;
        }   while (t != x);
    }
}

int main()
{
    FILE *in = fopen("ctc.in", "r");
    FILE *out = fopen("ctc.out", "w");

    int n, m;
    fscanf(in, "%d%d", &n, &m);
    for (int x, y; m > 0; m--)
    {
        fscanf(in, "%d%d", &x, &y);
        g[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
        if (v[i].index == 0)
            scc(i);

    fprintf(out, "%d\n", nr_sol);
    for (int i = 1; i <= n; i++)
    {
        fprintf(out, "%d ", sol[i]);
        if (new_line[i])
            fprintf(out, "\n");
    }
    fprintf(out, "\n");

    return 0;
}