Pagini recente » Cod sursa (job #3164858) | Cod sursa (job #2461953) | Cod sursa (job #440642) | Cod sursa (job #244794) | Cod sursa (job #2543242)
#include<bits/stdc++.h>
#define NMAX 100005
//in-out
std::ifstream f("ctc.in");
std::ofstream g("ctc.out");
//data
std::stack<int> firstDfsSt;
std::vector<int> G[NMAX];
std::vector<int> T[NMAX];
std::vector<int> comps[NMAX];
std::vector<bool> firstDfsViz(NMAX), inComp(NMAX);
int n, m, cnt = 0;
//readData
void readData(){
f >> n >> m;
int x, y;
for(int i = 0; i<m; i++){
f >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
}
void dfsFirst(int start){
firstDfsViz[start] = true;
for(auto& adj : G[start]){
if(!firstDfsViz[adj]){
dfsFirst(adj);
}
}
firstDfsSt.push(start);
}
void dfsSecond(int start){
inComp[start] = true;
for(auto& adj : T[start]){
if(!inComp[adj]){
dfsSecond(adj);
}
}
//std::cout << "CNT: " << cnt << "\nWill push back: " << start << '\n';
comps[cnt].push_back(start);
}
//solve
void solve(){
for(int i = 1; i<=n; i++){
if(!firstDfsViz[i]){
dfsFirst(i);
}
}
while(!firstDfsSt.empty()){
int node = firstDfsSt.top();
if(!inComp[node]){
dfsSecond(node);
cnt ++;
}else{
firstDfsSt.pop();
}
}
}
//printSolution
void printSolution(){
g << cnt << '\n';
for(int i = 0; i<cnt; i++){
for(const auto& elem : comps[i]){
g << elem << ' ';
}
g << '\n';
}
}
int main(){
readData();
solve();
printSolution();
return 0;
}