Cod sursa(job #754149)

Utilizator sunt_emoSunt emo sunt_emo Data 31 mai 2012 21:05:32
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <vector>
#include <fstream>
#include <stack>

#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"
#define N 100010

using namespace std;

vector<vector<int> > graf;
vector<vector<int> > sol;
stack<int> S;
int n,m,timp;
int id[N];
int low[N];
bool exist[N];

void read()
{
    graf.clear();
    ifstream in(FILEIN);
    in >> n >> m;
    for (int i = 0; i <= n; i++)
        graf.push_back(vector<int>());
    for (int i = 0; i < m; i++)
    {
        int x,y;
        in >> x >> y;
        graf[x].push_back(y);
    }
    in.close();
}

void tdfs(int u)
{
    id[u] = timp;
    low[u] = timp++;
    S.push(u);
    exist[u] = true;
    for (unsigned i = 0; i < graf[u].size(); i++)
    {
        int v = graf[u][i];
        if (id[v] == -1)
        {
            tdfs(v);
            if (low[v] < low[u])
                low[u] = low[v];
            continue;
        }
        if (exist[v] && id[v] < low[u])
            low[u] = id[v];
    }
    if (low[u] == id[u])
    {
        sol.push_back(vector<int>());
        do
        {
            int tmp = S.top();
            S.pop();
            exist[tmp] = false;
            sol.back().push_back(tmp);
            if (tmp == u)
                break;
        }
        while (1);
    }
}

void print()
{
    ofstream out(FILEOUT);
    int s = sol.size();
    out << s << endl;
    for (int i = 0; i < s; i++)
    {
        for (unsigned j = 0; j < sol[i].size(); j++)
            out << sol[i][j] << " ";
        out << endl;
    }
    out.close();
}

void tarjan()
{
    for (int i = 1; i <= n; i++)
    {
        id[i] = -1;
        exist[i] = false;
    }
    for (int i = 1; i <= n; i++)
        if (id[i] == -1)
            tdfs(i);
}

int main()
{
    read();
    tarjan();
    print();
}