Pagini recente » Cod sursa (job #456004) | Cod sursa (job #1026533) | Cod sursa (job #1113981) | Cod sursa (job #3192428) | Cod sursa (job #2798656)
#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;
for(int i = 0; i < la[start].size(); ++i){
if(!viz[la[start][i]]){
viz[la[start][i]] = 1;
dfs(la[start][i]);
}
}
s.push(start);
}
void dfsTrans (int start){
viz[start] = 2;
ctc[nrc].push_back(start);
for(int i = 0; i < lat[start].size(); ++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();
for(int i = 1; i <= nrc; ++i){
for(int j = 0; j < ctc[i].size(); ++j){
g << ctc[i][j] << " ";
}
g << "\n";
}
return 0;
}