Pagini recente » Profil Klushluck12 | Profil Amarinei | Istoria paginii runda/go_nathan/clasament | Ce am invatat din 3 ONI-uri | Cod sursa (job #652279)
Cod sursa(job #652279)
#include <fstream>
#include <vector>
using namespace std;
const int N=100005;
int a[N],b[N],stack[N],n;
bool use[N];
vector<int> a1[N],a2[N],rez[N];
ifstream in("ctc.in");
ofstream out("ctc.out");
/*
void dfs(int x,int val)
{
v[x]=val;
for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
if (!v[*i])
dfs(*i,val);
}
void dfs(vector<int> &rez,int x)
{
rez.push_back(x);
use[x]=true;
for (vector<int>::iterator i=b[x].begin();i!=b[x].end();i++)
if (!use[*i] && v[x]==v[*i])
dfs(rez,*i);
}
*/
void dfs(int x,vector<int> a[],int rez[],int val)
{
rez[x]=val;
for (vector<int>::iterator i=a[x].begin();i!=a[x].end();i++)
if (!rez[*i])
dfs(*i,a,rez,val);
}
void dfs(int x,int val)
{
a[x]=val;
stack[++stack[0]]=x;
for (vector<int>::iterator i=a1[x].begin();i!=a1[x].end();i++)
if (!a[*i])
dfs(*i,val);
}
void df(int x,int val)
{
b[x]=val;
for (vector<int>::iterator i=a2[x].begin();i!=a2[x].end();i++)
if (!b[*i])
df(*i,val);
}
int main()
{
int nr=0,x,y,val=0,m;
in>>n>>m;
while (m--)
{
in>>x>>y;
a1[x].push_back(y);
a2[y].push_back(x);
}
for (int i=1;i<=n;i++)
if (!a[i])
dfs(i,++val);
val=0;
for (int i=stack[0];i;i--)
if (!b[stack[i]])
df(stack[i],++val);
for (int i=1;i<=n;i++)
{
if (use[i])
continue;
rez[++nr].push_back(i);
for (int j=i+1;j<=n;j++)
if (a[i]==a[j] && b[i]==b[j])
{
use[j]=true;
rez[nr].push_back(j);
}
}
out<<nr<<"\n";
for (int i=1;i<=nr;i++)
{
for (vector<int>::iterator j=rez[i].begin();j!=rez[i].end();j++)
out<<(*j)<<" ";
out<<"\n";
}
return 0;
}