Pagini recente » Cod sursa (job #1613377) | Cod sursa (job #1006233) | Cod sursa (job #460891) | Cod sursa (job #895248) | Cod sursa (job #1922886)
/*#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> A[100001];
vector <int> AT[100001], C[100001];
int N;
int V[100001], VT[100001], L[100001];
int df1(int x){
vector <int> :: iterator it;
V[x] = 1;
for( it = A[x].begin(); it != A[x].end();it++ )
if( V[*it] == 0 )
df1(*it);
}
int df2(int x){
vector <int> :: iterator it;
VT[x] = 1;
for( it = AT[x].begin(); it != AT[x].end();it++ )
if( VT[*it] == 0 )
df2(*it);
}
int main()
{
int m, i, x, y, j, nrt;
f >> N;
f >> m;
for(i = 1; i <= m; i++){
f >> x >> y;
A[x].push_back(y);
AT[y].push_back(x);
}
nrt = 0;
for( i = 1; i <= N; i++ ){
if(L[i] == 0){
nrt++;
for(j = 1; j <= N; j++)
V[j] = VT[j] = 0;
df1(i);
df2(i);
for(j = 1; j <= N; j++)
if(V[j] == 1 && VT[j] == 1){
C[nrt].push_back(j);
L[j] = nrt;
}
}
}
vector <int> :: iterator it;
g << nrt << '\n';
for(i = 1; i <= nrt;i++){
for(it = C[i].begin(); it != C[i].end(); it++)
g << *it << " ";
g << '\n';
}
return 0;
}*/
#include <fstream>
#include <vector>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
int n,m,i,j,v1,v2;
vector <int> A[100001];
vector <int> AT[100001];
int nrc, C[100001], VIZ1[100001], VIZ2[100001];
void df1(int v)
{
vector <int> :: iterator it;
int i;
VIZ1[v]=1;
for (it=A[v].begin();it!=A[v].end();it++)
{
i=(*it);
if (VIZ1[i]==0)
df1(i);
}
}
void df2(int v)
{
vector <int> :: iterator it;
int i;
VIZ2[v]=1;
for (it=AT[v].begin();it!=AT[v].end();it++)
{
i=(*it);
if (VIZ2[i]==0)
df2(i);
}
}
int main()
{
fi>>n>>m;
for (i=1;i<=m;i++)
{
fi>>v1>>v2;
A[v1].push_back(v2);
AT[v2].push_back(v1);
}
nrc=0;
for (i=1;i<=n;i++)
if (C[i]==0)
{
nrc++;
for (j=1;j<=n;j++)
VIZ1[j]=VIZ2[j]=0;
df1(i);
df2(i);
for (j=1;j<=n;j++)
if (VIZ1[j]==1 && VIZ2[j]==1)
C[j]=nrc;
}
fo << nrc << '\n';
for(j = 1; j <= nrc; j++){
for (i=1;i<=n;i++)
if( C[i] == j )
fo<<i<<" ";
fo << '\n';
}
fi.close();
fo.close();
return 0;
}