Pagini recente » Cod sursa (job #2422798) | Cod sursa (job #2911190) | Cod sursa (job #1703768) | Cod sursa (job #2257829) | Cod sursa (job #2156620)
#include<fstream>
#include<list>
#include<bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 5;
list<int> adjList[NMAX], adjListTrans[NMAX], SCC[NMAX];
bitset<NMAX> vis;
int Stack[NMAX];
int nodesCnt, edgesCnt, StackLen, SCCCnt;
inline void readData(){
fin >> nodesCnt >> edgesCnt;
int from, to;
while(edgesCnt--){
fin >> from >> to;
adjList[from].push_back(to);
adjListTrans[to].push_back(from);
}
}
void topoSort(int node){
vis[node] = true;
for(const int &nextNode : adjList[node])
if(!vis[nextNode])
topoSort(nextNode);
Stack[++StackLen] = node;
}
inline void getOrder(){
int node;
for(node = 1; node <= nodesCnt; ++node)
if(!vis[node])
topoSort(node);
}
void DFS(int node){
vis[node] = false;
SCC[SCCCnt].push_back(node);
for(const int &nextNode : adjListTrans[node])
if(vis[nextNode])
DFS(nextNode);
}
inline void getSCC(){
int idx;
for(idx = StackLen; idx >= 1; --idx)
if(vis[Stack[idx]]){
++SCCCnt;
DFS(Stack[idx]);
}
}
inline void print(){
fout << SCCCnt << '\n';
int idx;
for(idx = 1; idx <= SCCCnt; ++idx){
for(const int &node : SCC[idx])
fout << node << ' ';
fout << '\n';
}
}
int main(){
readData();
getOrder();
getSCC();
print();
}