Cod sursa(job #989484)

Utilizator gunner_292Mihai Manolescu gunner_292 Data 25 august 2013 18:28:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include<fstream>
#include<list>

#define dmax 100003

using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

int n, m, sccNr;

list<list<int> >scc;
list<list<int> >::iterator it;
list<int>currentScc;
list<int>::iterator ir;

list<int>adj[dmax];
list<int>adjT[dmax];

list<int>sorted;

bool visited[dmax];


void dfs(int currentN)
{
    list<int>::iterator it;

    for(it = adj[currentN].begin(); it != adj[currentN].end(); it++)
    {
        if(visited[*it] == false)
        {
            visited[*it] = true;
            dfs(*it);
        }
    }

    sorted.push_front(currentN);
}

void dfsT(int currentN)
{
    list<int>::iterator it;

    currentScc.push_back(currentN);

    for(it = adjT[currentN].begin(); it != adjT[currentN].end(); it++)
    {
        if(visited[*it] == false)
        {
            visited[*it] = true;
            dfsT(*it);
        }
    }

}



int main()
{
    in>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int a, b;

        in>>a>>b;

        adj[a].push_back(b);
        adjT[b].push_back(a);
    }
    in.close();

    for(int i=1; i<=n; i++)
    {
        visited[i] = false;
    }

    for(int i=1; i<=n; i++)
    {
        if(visited[i] == false)
        {
            visited[i] = true;
            dfs(i);
        }
    }

    for(int i=1; i<=n; i++)
        visited[i] = false;

    for(ir = sorted.begin(); ir != sorted.end(); ir++)
    {
        if(visited[*ir] == false)
        {
            if(!currentScc.empty())
            {
                sccNr++;
                scc.push_back(currentScc);
                currentScc.clear();
            }

            visited[*ir] = true;
            dfsT(*ir);
        }
    }

    if(!currentScc.empty())
    {
        sccNr++;
        scc.push_back(currentScc);
        currentScc.clear();
    }

    out<<sccNr<<'\n';

    for(it = scc.begin(); it != scc.end(); it++)
    {
        for(ir = (*it).begin(); ir != (*it).end(); ir++)
            out<<*ir<<" ";

        out<<'\n';
    }

    out.close();
    return 0;
}