Pagini recente » Cod sursa (job #401893) | Cod sursa (job #763619) | Cod sursa (job #888215) | Cod sursa (job #582659) | Cod sursa (job #2827987)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int theNeighbours[105][105];
int theIdexOfNeig[105];
bool isVisited[105];
int visitedStack[1005];
int theStack[1005];
int dr;
int transposedNeighbours[105][105];
int trasposedIndexOfNeighbour[105];
int theComponents[105][105];
int sizeOfComponent[105];
int scc;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfs2(int node)
{
isVisited[node] = true;
for(int i=0;i< trasposedIndexOfNeighbour[node];i++)
{
int currNode = transposedNeighbours[node][i];
if(isVisited[currNode] == false)
{
theComponents[scc][sizeOfComponent[scc]] = currNode;
++sizeOfComponent[scc];
dfs2(currNode);
}
}
}
void dfs(int node)
{
isVisited[node] = true;
for(int i=0; i<theIdexOfNeig[node]; i++)
{
int currNode = theNeighbours[node][i];
if(isVisited[currNode] == false)
dfs(currNode);
}
theStack[dr] = node;
++dr;
}
int main()
{
//dfs
//faci array-ul cu visited\
//faci dfs pe transpus
//cand elimini o componenta care nu e visited ai o noua componenta
//tare conexa
int n,m;
fin>>n>>m;
for(int i=0; i<m; i++)
{
int x,y;
fin>>x>>y;
theNeighbours[x][theIdexOfNeig[x]] = y;
++theIdexOfNeig[x];
transposedNeighbours[y][trasposedIndexOfNeighbour[y]] = x;
++trasposedIndexOfNeighbour[y];
}
for(int i=1; i<=n; i++)
{
if(isVisited[i] == false)
dfs(i);
}
for(int i=1; i<=n; i++)
isVisited[i] = false;
int st=0;
--dr;
while(0 <= dr)
{
if(isVisited[theStack[dr]] == false)
{
sizeOfComponent[scc] = 0;
theComponents[scc][sizeOfComponent[scc]] = theStack[dr];
++sizeOfComponent[scc];
dfs2(theStack[dr]);
++scc;
}
--dr;
}
fout<<scc<<"\n";
for(int i=0;i<scc;i++)
{
sort(theComponents[i],theComponents[i]+sizeOfComponent[i]);
for(int j=0;j<sizeOfComponent[i];j++)
fout<<theComponents[i][j]<<" ";
fout<<"\n";
}
return 0;
}