Cod sursa(job #1029053)

Utilizator sziliMandici Szilard szili Data 14 noiembrie 2013 22:49:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.51 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <vector>

using namespace std;

typedef struct node{
    int index;
    int lowest;
} NODE;

int n,m;

vector<int> adjacencyList[100001];

int currentIndex = 1;
int isInStack[100001];

NODE seenOrder[100001];
stack<int> st;

vector< vector<int> > connectedComponents;

void readData(){

    scanf("%d %d", &n, &m);

    int from,to;
    for (int i=0; i<m; i++){
        scanf("%d %d", &from, &to);
        adjacencyList[from].push_back(to);
    }
}

int minn(int a, int b){
    if (a<b)
        return a;
    else
        return b;
}

void dfs(int currentNode){
    seenOrder[currentNode].index = currentIndex;
    seenOrder[currentNode].lowest = currentIndex;
    currentIndex++;

    //go through all of the adjacent nodes;
    for (int i=0; i<adjacencyList[currentNode].size(); i++){
        int nodeToBeVisited = adjacencyList[currentNode][i];

        if (seenOrder[nodeToBeVisited].index == 0){
            st.push(nodeToBeVisited);
			isInStack[nodeToBeVisited] = 1;
            dfs(nodeToBeVisited);
            seenOrder[currentNode].lowest = minn(seenOrder[nodeToBeVisited].lowest, seenOrder[currentNode].lowest);
        } else if (isInStack[nodeToBeVisited]){
            seenOrder[currentNode].lowest = minn(seenOrder[nodeToBeVisited].index, seenOrder[currentNode].lowest);
        }
    }

    //check if a new connected component has been found
    if (seenOrder[currentNode].index == seenOrder[currentNode].lowest){
        int stackNode;
        vector<int> componentNodes;

        do {
            stackNode = st.top();
            st.pop();
			isInStack[stackNode] = 0;

            componentNodes.push_back(stackNode);

        } while(stackNode != currentNode);

        connectedComponents.push_back(componentNodes);
    }

}


void tarjan(){

    for (int i=1; i<=n; i++){
        if (!seenOrder[i].index){
            isInStack[i]  = 1;
            st.push(i);
            dfs(i);
        }
    }

}

void outputResults(){

    printf("%d\n", connectedComponents.size());

    for (int i=0; i<connectedComponents.size(); i++){

        for (int j=0; j<connectedComponents[i].size(); j++){
            printf("%d ", connectedComponents[i][j]);
        }
        printf("\n");
    }

}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    readData();
    tarjan();
    outputResults();

    return 0;
}