Pagini recente » Cod sursa (job #1162304) | Cod sursa (job #824018) | Cod sursa (job #2684023) | Cod sursa (job #1033841) | Cod sursa (job #1029053)
#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;
}