Pagini recente » Cod sursa (job #3182954) | Cod sursa (job #3276537) | Cod sursa (job #2090204) | Cod sursa (job #57120) | Cod sursa (job #2928603)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
const int NMAX = 1e5;
vector <int> graf[NMAX + 1], revgraf[NMAX + 1];
vector <int> viz[NMAX + 1];
vector <int> ctcorder;
bool marked[NMAX + 1];
void dfs (vector<int>* graf, int node, vector<int>& viz){
marked[node] = 1;
int _Size = graf[node].size();
for (int i = 0; i < _Size; i++){
if (!marked[graf[node][i]])
dfs(graf, graf[node][i], viz);
}
viz.push_back(node);
}
int main(){
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
for (int i = 0; i < m; i++){
int a, b;
fin >> a >> b;
graf[a].push_back(b);
revgraf[b].push_back(a);
}
for (int i = 1; i <= n; i++){
if (!marked[i])
dfs (graf, i, ctcorder);
}
memset (marked, 0, sizeof(marked));
int nrofcomp = 0;
int currnode;
while (!ctcorder.empty()){
currnode = ctcorder.back();
ctcorder.pop_back();
if (!marked[currnode]){
dfs (revgraf, currnode, viz[nrofcomp]);
++nrofcomp;
}
}
fout << nrofcomp << "\n";
for (int i = 0; i < nrofcomp; i++){
int size_ = viz[i].size();
for (int node = 0; node < size_; node ++)
fout << viz[i][node] << " ";
fout << "\n";
}
return 0;
}