Pagini recente » Cod sursa (job #622108) | Cod sursa (job #3145995) | Cod sursa (job #2349708) | Cod sursa (job #2908175) | Cod sursa (job #2204031)
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMAX], T[NMAX], strong_comp[NMAX];
bool viz[NMAX], in_com[NMAX];
stack<int> st;
int n, m, nr_com = 0;
void read_data(){
f >> n >> m;
for(int i = 1; i<=m; i++){
int x, y;
f >> x >> y;
G[x].pb(y);
T[y].pb(x);
}
}
void dfs(int src){
viz[src] = true;
for(const auto & node : G[src]){
if(!viz[node]){
dfs(node);
}
}
st.push(src);
}
void dfs_t(int src){
in_com[src] = true;
for(const auto& node : T[src]){
if(!in_com[node]){
dfs_t(node);
}
}
strong_comp[nr_com].pb(src);
}
void solve(){
for(int i = 1; i<=n; i++){
if(!viz[i]){
dfs(i);
}
}
while(!st.empty()){
auto node = st.top();
if(!in_com[node]){
nr_com ++;
dfs_t(node);
}
st.pop();
}
g << nr_com << '\n';
for(int i = 1; i<=nr_com; i++){
for(const auto& node : strong_comp[i]){
g << node << ' ';
}
g << '\n';
}
}
int main(){
read_data();
solve();
return 0;
}