Pagini recente » Cod sursa (job #3237155) | Cod sursa (job #1346389) | Cod sursa (job #61019) | Cod sursa (job #2687036) | Cod sursa (job #2925852)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
vector <vector<int> > AdjacencyList, AdjacencyListT, AllCTC;
stack <int> nodeOrder;
vector <bool> visited;
void DFS(int Node, vector<vector<int> > list){
visited[Node] = true;
for(int i = 0; i < list[Node].size(); i++){
int NodeNext = list[Node][i];
if(!visited[NodeNext])
DFS(NodeNext,list);
}
nodeOrder.push(Node);
}
void DFST(int Node, vector<vector<int> > list, vector<int>&CTC){
CTC.push_back(Node);
visited[Node] = true;
for(int i = 0; i < list[Node].size(); i++){
int NodeNext = list[Node][i];
if(!visited[NodeNext])
DFST(NodeNext,list, CTC);
}
}
int main() {
fin >> N >> M;
cout << N << M;
for(int i = 0; i <= N; i++){
AdjacencyList.push_back(vector<int>());
AdjacencyListT.push_back(vector<int>());
visited.push_back(false);
}
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 < AdjacencyList.size(); i++)
if(!visited[i])
DFS(i,AdjacencyList);
// Reset the visited vector
for(int i = 0; i < visited.size(); i++)
visited[i] = 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;
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(int j = 0; j < AllCTC[i].size(); j++)
fout << AllCTC[i][j] << " ";
fout << endl;
}
fin.close();
fout.close();
return 0;
}