Pagini recente » Cod sursa (job #2766154) | Cod sursa (job #1447459) | Cod sursa (job #2555993) | Cod sursa (job #2137058) | Cod sursa (job #2798666)
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
vector <int> la[NMAX], lat[NMAX], ctc[NMAX];
stack <int> s;
int nrc = 0;
int n, m;
int viz[NMAX];
void dfs(int start){
viz[start] = 1;
int nrv = la[start].size();
for(int i = 0; i < nrv; ++i){
if(!viz[la[start][i]]){
dfs(la[start][i]);
}
}
s.push(start);
}
void dfsTrans (int start){
viz[start] = 2;
ctc[nrc].push_back(start);
int nrv = lat[start].size();
for(int i = 0; i < nrv; ++i){
if(viz[lat[start][i]] == 1){
dfsTrans(lat[start][i]);
}
}
}
void solve(){
for(int i = 1; i <= n; ++i){
if(!viz[i]){
dfs(i);
}
}
while(!s.empty()){
int k = s.top();
if(viz[k] == 1){
nrc++;
dfsTrans(k);
}
s.pop();
}
}
int main()
{
ifstream f("ctc.in");
f >> n >> m;
for(int i = 0; i <= m; ++i){
int a, b;
f >> a >> b;
la[a].push_back(b);
lat[b].push_back(a);
}
f.close();
ofstream g("ctc.out");
solve();
g << nrc << "\n";
for(int i = 1; i <= nrc; ++i){
for(int j = 0; j < ctc[i].size(); ++j){
g << ctc[i][j] << " ";
}
g << "\n";
}
return 0;
}