Pagini recente » Cod sursa (job #1315733) | Cod sursa (job #429948) | Cod sursa (job #2447076) | Cod sursa (job #686870) | Cod sursa (job #2927375)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define MAXN 100005
int N, M;
vector <int> AdjacencyList[MAXN], AdjacencyListT[MAXN];
vector <vector <int>> AllCTC;
stack <int> nodeOrder;
vector <bool> visited;
void DFS(int Node, vector<int> *list){
vector <int>::iterator it;
visited[Node] = true;
for(it = list[Node].begin(); it != list[Node].end(); it++){
if(!visited[*it])
DFS(*it,list);
}
nodeOrder.push(Node);
}
void DFST(int Node, vector<int> *list, vector<int>&CTC){
vector <int>::iterator it;
CTC.push_back(Node);
visited[Node] = true;
for(it = list[Node].begin(); it != list[Node].end(); it++){
if(!visited[*it])
DFST(*it,list, CTC);
}
}
int main() {
vector <int>::iterator it;
fin >> N >> M;
visited.resize(N+1);
for(int i = 0; i < M; i++){
int x, y;
fin >> x >> y;
AdjacencyList[x].push_back(y);
AdjacencyListT[y].push_back(x);
}
// Use DFS to create the stack that contains the nodes
// in the order of how fast they've been finalized by the DFS
for(int i = 1; i <= N; i++)
if(!visited[i])
DFS(i,AdjacencyList);
// Reset the visited vector
visited.assign(visited.size(),false);
// Traverse each node of the stack and apply DFS
// - all the nodes reached from that search create a strongly connected component
// - display it
int NodeCurrent, NrCTC = 0;
while(!nodeOrder.empty()){
NodeCurrent = nodeOrder.top();
nodeOrder.pop();
if(!visited[NodeCurrent]){
vector <int> CTC;
DFST(NodeCurrent, AdjacencyListT, CTC);
AllCTC.push_back(CTC);
}
}
fout << AllCTC.size() << endl;
for( int i = 0; i < AllCTC.size(); i++){
for(it = AllCTC[i].begin(); it != AllCTC[i].end(); it++)
fout << *it << " ";
fout << endl;
}
fin.close();
fout.close();
return 0;
}