Pagini recente » Cod sursa (job #1274496) | Cod sursa (job #2276165) | Cod sursa (job #2462091) | Cod sursa (job #2204597) | Cod sursa (job #2087085)
#include <bits/stdc++.h>
#define NM 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, ctc[NM], nrc;
bool viz1[NM], viz2[NM];
vector <int> G[NM], GT[NM];
void df1(int x)
{
viz1[x] = 1;
for(int i=0; i < (int)G[x].size(); ++i)
if(viz1[G[x][i]] == 0)
df1(G[x][i]);
}
void df2(int x) ///graful transpus
{
viz2[x] = 1;
for(int i=0; i < (int)GT[x].size(); ++i)
if(viz2[GT[x][i]] == 0)
df2(GT[x][i]);
}
int main()
{
int i , j , m;
f >> n >> m;
while( m-- ) {
f >> i >> j;
G[i].push_back(j);
GT[j].push_back(i); ///graful transpus
}
for(int i = 1 ; i <= n ; ++i)
if(ctc[i] == 0){
for(int j = 1; j <= n ; ++j)
viz1[j] = viz2[j] = 0;
nrc ++;
df1(i);
df2(i);
for(int j = 1; j <= n ; ++j)
if(viz1[j] == 1 && viz2[j] == 1)
ctc[j] = nrc;
}
g << nrc << "\n";
for(int i=1; i<=nrc; ++i){
for(int j=1; j<=n; ++j)
if (ctc[j] == i) g << j << " ";
g << '\n';
}
return 0;
}