Pagini recente » Cod sursa (job #1231227) | Cod sursa (job #2524118) | Cod sursa (job #1080637) | Cod sursa (job #1875060) | Cod sursa (job #2678675)
//
// main.cpp
// ctc
//
// Created by Radu Costache on 28/11/2020.
// Copyright © 2020 Radu Costache. All rights reserved.
//
#include <stdio.h>
#include <vector>
#include <cstring>
#include <stack>
#define NMAX 100005
using namespace std;
int n, m, ctc;
stack <int> st;
vector <int> v1[NMAX];
vector <int> v2[NMAX];
vector <int> ans[NMAX];
vector<int> comp;
void dfs1(int);
void dfs2(int);
bool viz[NMAX], viz1[NMAX], viz2[NMAX];
int main(int argc, const char * argv[]) {
// insert code here...
FILE *f = fopen("ctc.in","r");
FILE *g = fopen("ctc.out", "w");
fscanf(f, "%d %d\n", &n, &m);
while (m--) {
int x, y;
fscanf(f, "%d %d\n", &x, &y);
v1[x].push_back(y);
v2[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (!viz1[i]) {
dfs1(i);
}
}
while (!st.empty()) {
if (!viz2[st.top()]) {
++ctc;
dfs2(st.top());
}
st.pop();
}
fprintf(g, "%d\n",ctc);
for (int i = 1; i <= ctc; ++i) {
for (auto it:ans[i])
fprintf(g, "%d ", it);
fprintf(g, "\n");
}
return 0;
}
void dfs1(int node) {
viz1[node] = 1;
for (auto it:v1[node])
if (viz1[it] == 0) {
dfs1(it);
}
st.push(node);
}
void dfs2(int node) {
viz2[node] = 1;
ans[ctc].push_back(node);
for (auto it:v2[node])
if (viz2[it] == 0) {
dfs2(it);
}
}