Pagini recente » Cod sursa (job #823675) | Cod sursa (job #3291038) | Cod sursa (job #1224646) | Cod sursa (job #1396373) | Cod sursa (job #2209890)
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMAX], T[NMAX], comp[NMAX];
bool viz[NMAX], in_comp[NMAX];
stack<int> st;
int nrc, n, m;
void read_data(){
f >> n >> m;
for(int i = 1; i<=m; i++){
int x, y;
f >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
}
void dfs_g(int node){
viz[node] = true;
for(const auto& adj:G[node]){
if(!viz[adj]){
dfs_g(adj);
}
}
st.push(node);
}
void dfs_t(int node){
in_comp[node] = true;
for(const auto& adj:T[node]){
if(!in_comp[adj]){
dfs_t(adj);
}
}
comp[nrc].push_back(node);
}
void solve(){
for(int i = 1; i<=n; i++){
if(!viz[i]){
dfs_g(i);
}
}
while(!st.empty()){
int node = st.top();
if(!in_comp[node]){
dfs_t(node);
nrc++;
}
else{
st.pop();
}
}
g << nrc<< '\n';
for(int i = 0; i<nrc; i++){
for(const auto& nr : comp[i]){
g << nr << ' ' ;
}
g << '\n';
}
}
int main(){
read_data();
solve();
return 0;
}