Pagini recente » Cod sursa (job #3342645) | Cod sursa (job #3328304) | Cod sursa (job #3342641) | Cod sursa (job #1536414) | Cod sursa (job #1447591)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void DFSP(vector<vector<int> >& g, stack<int>& s, vector<int>& visited, int n)
{
visited[n] = 1;
for (int i = 0; i < g[n].size(); i++)
{
if (visited[g[n][i]] == 0){
DFSP(g,s,visited,g[n][i]);
}
}
s.push(n);
}
void DFSM(vector<vector<int> >& gt, stack<int>& s, vector<int>& visited, vector<int>& where,vector<vector<int> >& result, int n, int which)
{
where[n] = which;
for (int i = 0; i < gt[n].size(); i++){
if (where[gt[n][i]] == -1){
DFSM(gt,s,visited,where,result,gt[n][i],which);
}
}
result[which].push_back(s.top());
s.pop();
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, a, b, k = 0;
f >> N >> M;
vector<vector<int> > G(N+1), GT(N+1), result(N+1);
vector<int> visited(N+1, 0), where(N+1,-1);
stack<int> s;
for (int i = 0; i < M; i++){
f >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
for (int i = 1; i <= N; i++){
if (visited[i] == 0)
DFSP(G, s, visited, i);
}
int count = 0, leader;
while (!s.empty()){
count++;
leader = s.top();
DFSM(GT,s,visited,where,result,leader,count);
}
g << count << endl;
for (int i = 1; i <= count; i++){
for (int j = 0; j < result[i].size(); j++)
g << result[i][j] << " ";
g << endl;
}
f.close();
g.close();
return 0;
}