Pagini recente » Cod sursa (job #479703) | Cod sursa (job #2729015) | Cod sursa (job #2518100) | Cod sursa (job #635348) | Cod sursa (job #2864368)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int>a[100005];
vector<int>a2[100005];
int viz[100005];
int viz2[100005];
int viz3[100005];
int cnt, cnt2;
int n, m;
int rasp[100005];
void dfs(int x)
{
viz[x] = 1;
for(int i = 0; i < a[x].size() ; i++)
{
//cout << i << " " << a[x][i] << " ";
if(viz[a[x][i]] == 0)
{
dfs(a[x][i]);
}
}
rasp[cnt] = x;
cnt++;
}
void dfs2(int x)
{
viz2[x] = 1;
for(int i = 0; i < a2[x].size() ; i++)
{
if(viz2[a2[x][i]] == 0)
{
dfs2(a2[x][i]);
}
}
}
void dfs3(int x)
{
out << x << " ";
viz3[x] = 1;
for(int i = 0; i < a2[x].size() ; i++)
{
if(viz3[a2[x][i]] == 0)
{
dfs3(a2[x][i]);
}
}
}
int main()
{
int x, y;
in >> n >> m;
for(int i = 1; i <= m; i++)
{
in >> x >> y;
a[x].push_back(y);
a2[y].push_back(x);
}
for(int i = 1; i <= n; i++)
{
if(viz[i] == 0)
{
dfs(i);
}
}
for(int i = cnt - 1; i >= 0; i--)
{
if(viz2[rasp[i]] == 0)
{
cnt2++;
dfs2(rasp[i]);
}
}
out << cnt2 << "\n";
for(int i = cnt - 1; i >= 0; i--)
{
if(viz3[rasp[i]] == 0)
{
dfs3(rasp[i]);
out << "\n";
}
}
return 0;
}
/*
algoritim
iti creezi si graful transpus (muchiile au directie inversa)
faci sortare topologica pe graful normal
parcurgi nodurile sortate topologic si faci dfs pe graful transpus ca la algoritmul de componente conexe
*/