Cod sursa(job #754125)

Utilizator sunt_emoSunt emo sunt_emo Data 31 mai 2012 19:36:47
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <vector>
#include <fstream>
#include <stack>

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

using namespace std;

vector<vector<int> > graf;
vector<vector<int> > sol;
int n,m;

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,int &timp,int id[],int low[],stack<int> &S,bool exist[])
{
    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,timp,id,low,S,exist);
            if (low[v] < low[u])
                low[u] = low[v];
            continue;
        }
        if (exist[v] && low[v] < low[u])
            low[u] = low[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()
{
    int id[n + 1];
    int low[n + 1];
    bool exist[n + 1];
    for (int i = 1; i <= n; i++)
    {
        id[i] = -1;
        exist[i] = false;
    }
    int timp = 0;
    stack<int> S;
    for (int i = 1; i <= n; i++)
        if (id[i] == -1)
            tdfs(i,timp,id,low,S,exist);
}

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