Pagini recente » Cod sursa (job #1096425) | Clasamentul arhivei de probleme | Cod sursa (job #2532434) | Cod sursa (job #2513141) | Cod sursa (job #3300474)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,a,b, mark[100005], mark2[100005],nr;
vector <int> v[100005], w[100005];
vector <int> rasp[100005];
stack <int> S;
void DFS(int nod){
for (int i = 0; i < v[nod].size(); i++){
if (!mark[v[nod][i]]){
mark[v[nod][i]] = 1;
DFS(v[nod][i]);
}
}
S.push(nod);
}
void DFS2(int nod){
rasp[nr].push_back(nod);
for (int i = 0; i < w[nod].size(); i++){
if (!mark2[w[nod][i]]){
mark2[w[nod][i]] = 1;
DFS2(w[nod][i]);
}
}
}
int main()
{
fin>>n>>m;
for (int i = 1; i <= m; i++){
fin>>a>>b;
v[a].push_back(b);
w[b].push_back(a);
}
for (int j = 1; j <= n; j++){
if(!mark[j]){
mark[j] = 1;
DFS(j);
}
}
while(!S.empty()){
int j = S.top();
if(!mark2[j]){
mark2[j] = 1;
nr++;
DFS2(j);
}
S.pop();
}
fout << nr << '\n';
for (int i = 1; i <= nr; i++){
for (int j = 0; j < rasp[i].size(); j++){
fout << rasp[i][j] << " ";
}
fout << '\n';
}
return 0;
}