Pagini recente » Cod sursa (job #1468237) | Cod sursa (job #3129347) | Cod sursa (job #2519688) | Cod sursa (job #2262780) | Cod sursa (job #2571171)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
#define MATA 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>graph[100005];
vector<int>cc[100005];
stack<int>myStack;
int N, M, x, y, ID, id[100005], lowlink[100005], ccNum;
bitset<MATA> onStack;
void tarjanDFS(int thisNode){
id[thisNode] = lowlink[thisNode] = ++ID;
myStack.push(thisNode);
onStack[thisNode] = true;
for(auto nextNode: graph[thisNode]){
if(!id[nextNode]){
tarjanDFS(nextNode);
lowlink[thisNode] = min(lowlink[thisNode], lowlink[nextNode]);
}
else if(onStack[nextNode])
lowlink[thisNode] = min(lowlink[thisNode], lowlink[nextNode]);
}
if(id[thisNode] == lowlink[thisNode]){
ccNum++;
int z;
do{
z = myStack.top(); myStack.pop();
//lowlink[myStack.top()] = id[thisNode];
cc[ccNum].push_back(z);
onStack[z] = false;
} while(z != thisNode);
}
}
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(!id[i])
tarjanDFS(i);
}
fout << ccNum << endl;
for(int i = 1; i <= ccNum; i++){
for(auto x: cc[i])
fout << x << ' ';
fout << endl;
}
return 0;
}