Pagini recente » Cod sursa (job #564312) | Cod sursa (job #1543877) | Cod sursa (job #2850604) | Cod sursa (job #549177) | Cod sursa (job #2566876)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>graph[10005];
vector<int>cc[10005];
stack<int>myStack;
int N, M, x, y, ID, visited[10005], id[10005], lowlink[10005], onStack[10005], ccNum;
void tarjanDFS(int thisNode){
id[thisNode] = lowlink[thisNode] = ++ID;
myStack.push(thisNode);
onStack[thisNode] = true; visited[thisNode] = true;
for(auto nextNode: graph[thisNode]){
if(!visited[nextNode])
tarjanDFS(nextNode);
if(onStack[nextNode])
lowlink[thisNode] = min(lowlink[thisNode], lowlink[nextNode]);
}
if(id[thisNode] == lowlink[thisNode]){
ccNum++;
do{
lowlink[myStack.top()] = id[thisNode];
cc[ccNum].push_back(myStack.top());
onStack[myStack.top()] = false;
myStack.pop();
}while(myStack.top() != thisNode);
cc[ccNum].push_back(myStack.top());
myStack.pop();
}
}
int main()
{
fin >> N >> M;
for(int i = 1; i <= M; i++){
fin >> x >> y;
graph[x].push_back(y);
}
for(int i = 1; i <= N; i++){
if(!visited[i])
tarjanDFS(i);
}
fout << ccNum << endl;
for(int i = 1; i <= ccNum; i++){
for(auto x: cc[i])
fout << x << ' ';
fout << endl;
}
return 0;
}