Pagini recente » Cod sursa (job #1595583) | Cod sursa (job #2510053) | Cod sursa (job #1509987) | Cod sursa (job #3123353) | Cod sursa (job #3243145)
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;
const int nmax = 1e5;
vector <int> graf[nmax + 1];
vector <int> revgraf[nmax + 1];
vector <int> ctc;
vector <int> viz[nmax + 1];
int ctcnr;
bool marked[nmax + 1];
void dfs (vector <int> *graf, int node, vector<int>& viz){
marked[node] = true;
for (auto neighbour : graf[node]){
if (!marked[neighbour])
dfs (graf, neighbour, viz);
}
viz.push_back(node);
}
int main(){
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; i++){
int x, y;
fin >> x >> y;
graf[x].push_back(y);
revgraf[y].push_back(x);
}
for (int i = 1; i <= n; i++){
if (!marked[i]){
dfs (graf, i, ctc);
}
}
memset (marked, 0, sizeof(marked));
while (!ctc.empty()){
int topnode = ctc.back();
ctc.pop_back();
if (!marked[topnode]){
dfs (revgraf, topnode, viz[ctcnr]);
ctcnr ++;
}
}
fout << ctcnr << "\n";
while (ctcnr--){
for (auto sol: viz[ctcnr]){
fout << sol << " ";
}
fout << "\n";
}
return 0;
}