Pagini recente » Cod sursa (job #1021713) | Cod sursa (job #256065) | Cod sursa (job #2134888) | Cod sursa (job #1895109) | Cod sursa (job #3275437)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> direct[100001];
vector<int> invers[100001];
int vizd[100001], vizi[100001], comp[100001];
void dfs(int x, vector<int> v[100001], int viz[100001])
{
viz[x] = 1;
int k = v[x].size();
for(int i = 0; i < k; i++)
{
if(viz[ v[x][i] ] == 0 && comp[ v[x][i] ] == 0 )
{
dfs( v[x][i], v, viz);
}
}
}
int main()
{
int n , m;
in >> n >> m;
for(int i = 1 ; i <= m; i ++)
{
int x , y; // x->y
in >> x >> y;
direct[x].push_back(y);
invers[y].push_back(x);
}
int nrc=0;
for(int i = 1; i <= n; i++)
{
if(comp[i]==0)
{
nrc++;
dfs(i, direct, vizd);
dfs(i, invers, vizi);
for(int j = 1 ; j <= n; j++)
{
if(vizd[j] == 1 && vizi[j] == 1)
{
comp[j] = nrc;
}
vizd[j] = vizi[j] = 0;
}
}
}
out<<nrc<<'\n';
for(int i = 1; i <= nrc; i++)
{
for(int j = 1; j <= n; j++)
{
if(comp[j] == i)
{
out << j << " ";
}
}
out << "\n";
}
return 0;
}