Pagini recente » Cod sursa (job #1312353) | Cod sursa (job #3151072) | Cod sursa (job #321741) | Cod sursa (job #1835668) | Cod sursa (job #1561780)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[100001];
vector<int> T[100001];
vector<int> sol[100001];
int viz[100001];
int vizT[100001];
int vizG[100001];
int comp,n,m;
void DFG(int nod)
{
if(!vizG[nod])
{
vizG[nod] = true;
for(vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
DFG(*it);
}
}
void DFT(int nod)
{
if(!vizT[nod])
{
vizT[nod] = true;
for(vector<int>::iterator it = T[nod].begin(); it != T[nod].end(); ++it)
DFT(*it);
}
}
void intersect()
{
bool flag = false;
for(int i = 1; i <= m; ++i)
if(vizG[i] == true && vizT[i] == true)
{
flag = true;
viz[i] = true;
sol[comp].push_back(i);
}
if(flag) comp++;
}
int main()
{
int x,y;
f >> n >> m;
for(int i = 1; i <= m; ++i)
{
f >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
{
if(!viz[i])
{
DFG(i);
DFT(i);
intersect();
memset(vizG,false,100001);
memset(vizT,false,100001);
}
}
g << comp << "\n";
for(int i = 0; i < comp; ++i)
{
for(vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
g << *it << " ";
g << "\n";
}
return 0;
}